## Greedy Heuristics with an Altered Subset Sum/Partition Problem

Say we have a constant-time function that accepts some integer set. The function outputs True if we can split the integers into two subsets of an equal sum. If we can’t partition the integers given, the function outputs False.

Suppose we can use this function at any time, with any set of integers. Can we make a greedy algorithm using this function that will output one of the specific subsets that sum to half of a particular positive integer set?

The heart of the question: If we know at any time the boolean result of canPartition() on any set of integers, can we greedily use that to output the specific values of a partition?

## What’s a good way to find a near optimal or optimal state in a graph without heuristics or values?

What’s a good way to find the optimal solution in a graph with no heuristics or knowledge of the value of that state until we are there? Is there a good way to perhaps create an estimate? I’ve looked into things like value iteration and policy iteration as well as Q-learning, but what if another issue is evaluating the true reward of a state is very costly?

## Comparison of constructive and local-search heuristics for TSP

In my high school class, we are currently looking at evaluating heuristic methods for intractable problems – especially TSP.

My question is what is the advantages or disadvantages of using a constructive heuristic (like Nearest-Neighbour) compared to local search (something like 2-opt from some research?)

Thank you

## Good examples of consistent/admissible heuristics in non-graphical domains?

I’m preparing lectures for intro to AI, and would like to give non-boring examples of heuristic functions.

Does anyone know examples of non-trivial consistent/admissible heuristics in non-geographic domains? Ones that appear in recent research papers are preferable.

Many thanks!

## Heuristics vs meta-heuristics vs hyper-heuristics?

The wikipedia page on meta-heuristics states that they are “heuristics designed to find, generate, or select a heuristic”.

The wikipedia page on hyper-heuristics states that they are “heuristic search methods that seeks to automate […] the process of selecting, combining, generating or adapting several simpler heuristics”.

Moreover, it also states that “The fundamental difference between metaheuristics and hyper-heuristics is that most implementations of metaheuristics search within a search space of problem solutions, whereas hyper-heuristics always search within a search space of heuristics.”

This leaves me confused: it seems like the hyper heuristic page is contradicting the meta-heuristic page. How can a meta-heuristic search for heuristics, if its search space is the problem space rather than the space of heuristics?

What really is the difference between metaheuristics and hyperheuristics?

## Boundary Harnack inequality heuristics

What is the heuristic idea of the proof of the boundary Harnack inequality presented in the appendix of Caffarelli’s 1998 lectures on the obstacle problem?

## Map coloring with MRV and Degree heuristics in Python

I am relatively new to Python. I wrote this solution to the well known map coloring problem and also implemented the MRV and Degree heuristics. Here, I am considering the map of Australia – `['WA', 'NT', 'SA', 'Q', 'NSW', 'V', 'T']` and 3 given colors – `['R','G', 'B']`

``# choosing first node with degree heruistics # applying MRV with backtracking  from enum import Enum import pdb  class Color(Enum):     RED = 1     GREEN = 2     BLUE = 3  class Graph:     def __init__(self, totalNodes, adjacencyList, color):         self.totalNodes = totalNodes         self.adjacencyList = adjacencyList         self.color = color         self.nodeSequence = [""]*totalNodes      def isSafe(self, node, c):         for i in range(len(self.adjacencyList[node])):             if(self.color[self.adjacencyList[node][i]] == c):                 return False         return True       def graphColorUtil(self, node, colorLimit):         if node == '':             # check and color any uncolored node             for key, value in self.color.items():                 if value == 0:                     self.graphColorUtil(key, colorLimit)             return True          # pdb.set_trace()         for c in range(1, colorLimit+1):             if(self.isSafe(node, c) == True):                 self.color[node] = c                 nextNode = self.getNodeWithMRV(node, colorLimit)                 if(self.graphColorUtil(nextNode, colorLimit) == True):                     return True                 else:                     self.color[node] = 0          return False       def graphColoring(self, colorLimit):         # pdb.set_trace()         startNode = self.pickNode('')         if(self.graphColorUtil(startNode, colorLimit) == True):             return True         else:             print("Solution does not exists")             return False       # pick node using MRV     def pickNode(self, initialNode):         maxCount = 0         selectedNode = ''         # the very first node         if (initialNode == ''):             for node, neighbourList in self.adjacencyList.items():                 if (len(neighbourList) > maxCount and self.color[node] == 0):                     maxCount = len(neighbourList)                     selectedNode = node         # the other nodes         else:             for i in range(len(self.adjacencyList[initialNode])):                 childNode = self.adjacencyList[initialNode][i]                 if (self.color[childNode] == 0 and len(self.adjacencyList[childNode]) > maxCount):                     maxCount = len(self.adjacencyList[childNode])                     selectedNode = childNode          return selectedNode       def getNodeWithMRV(self, parentNode, colorLimit):         selectedNode = ''          for i in range(len(self.adjacencyList[parentNode])):             childNode = self.adjacencyList[parentNode][i]             countColor = 0             for c in range(1, colorLimit+1):                 if(self.isSafe(childNode, c) == True):                     countColor += 1             if (countColor < minCount):                 selectedNode = childNode          return selectedNode  # driver code def main():     adjacencyList = {         'WA': ['NT', 'SA'],         'NT': ['WA', 'SA', 'Q'],         'SA': ['WA', 'NT', 'Q', 'NSW', 'V'],         'Q': ['NT', 'SA', 'NSW'],         'NSW': ['SA', 'Q', 'V'],         'V': ['SA', 'T', 'NSW'],         'T': ['V']     };      color = {         'WA': 0,         'NT': 0,         'SA': 0,         'Q': 0,         'NSW': 0,         'V': 0,         'T': 0     };      g = Graph(7, adjacencyList, color)     colorLimit = 3     g.graphColoring(colorLimit)      for node, color in g.color.items():         print(node, Color(color).name) main() ``

What could be the possible ways to refactor this code? I am also interested for feedback on Python code style in general.

## Heuristics to Identify CSRF from Web Access Log File

I am new here in security.

I want to identify suspicious users on web application by analyzing web access log file. For this, I am considering CSRF attack.

For this purpose, I am generating some heuristic (possible) rules for identification of suspicious users from web log. I am not confident but still guessed some rules,

In web log,

1. Referrer URL is blank or not equal to requested URL’s domain name.

for e.g.

``192.168.4.6 ­ ­ [10/Oct/2007:13:55:36 ­0700] "GET /trx.php? amt=100&toAcct=12345 HTTP/1.0" 200 4926 "http://www.attacker.com/freestuff.php" "Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1; .NET CLR 1.1.4322)" ``

Two fields are important here, the requested URL (`/trx.php? amt=100&toAcct=12345`) and the referer (“`http://www.attacker.com/freestuff.php`“). Usually, the referer is an URL from the same site (`www.bank.com`). Here is a sample perl snippet, how this could be detected:

``# assuming \$  referer is set with the, well, referer if ( ( \$  referer ne '­' ) && ( \$  referer !~ /^https?:\/\/www.bank.com\/(login|overview|trx)\.jsp/ ) )  {     # handle XSRF attack     print(“XSRF attack: \$  referer\n”); } ``

(If the CSRF token is not sent, or if an invalid CSRF token is sent in requests that require a CSRF token). So, here checking of 403 status will be included. Because token can not get checked in log file.

3. By measuring the time ­difference of the requests of a user.

If there was no user input for several minutes and then suddenly some transfer requests are coming in, it could be an indicator that this request was triggered by something/someone else. Here, it will be needed to check time difference upto the threshold value from same IP address.(Along with this, If values are present after `?` symbol and if these would be ‘pass’,’password’,’amount’,’amt’,’money’, or any link and if User request status would be 200 i.e. successful or OK).

4. Multiple POST request (repeatation) from single IP address also results into CSRF.

Idempotent methods and web applications Methods PUT and DELETE are defined to be idempotent, meaning that multiple identical requests should have the same effect as a single request (note that idempotent refers to the state of the system after the request has completed, so while the action the server takes (e.g. deleting a record) or the response code it returns may be different on subsequent requests, the system state will be the same every time[citation needed]). Methods GET, HEAD, OPTIONS and TRACE, being prescribed as safe, should also be idempotent, as HTTP is a stateless protocol.

In contrast, the POST method is not necessarily idempotent, and therefore sending an identical POST request multiple times may further affect state or cause further side effects (such as financial transactions). In some cases this may be desirable, but in other cases this could be due to an accident, such as when a user does not realize that their action will result in sending another request, or they did not receive adequate feedback that their first request was successful. While web browsers may show alert dialog boxes to warn users in some cases where reloading a page may re-submit a POST request, it is generally up to the web application to handle cases where a POST request should not be submitted more than once.

5. A website might allow deletion of a resource through a URL such as `http://example.com/article/1234/delete`, which, if arbitrarily fetched, even using GET, would simply delete the article. (I don’t know what to do here)

I know, CSRF identification from log file is difficult, so, I am mentioning possible ways (i.e. heuristics) here. If wrong, correction in this is required. Any more rules/help would be appreciated.