Trick-or-Treat Algorithms

[Shalmanese]

@ultrafilter

As promised, here’s the proof that optimizing your candy take is NP-complete.

An instance of the Halloween loot problem is a 5-tuple (H, C, v, M, k), whose elements break down as follows:[ul][li]H is the set of houses.[]C [symbol]Î[/symbol] H [symbol]´[/symbol] H [symbol]®[/symbol] Z[sup]+[/sup] is the cost function for moving from house to house.[]v [symbol]Î[/symbol] H [symbol]®[/symbol] Z is the value function for the candy at a given house. As mentioned above, v(h) = 0 if house h has been visited.[]M is the maximum cost.[]k is the target for the total value.[/ul]A solution to an instance of the Halloween loot problem is a sequence of houses h[sub]1[/sub], h[sub]2[/sub], …, h[sub]n[/sub] with [symbol]S[/symbol][sub]i = 1[/sub][sup]n - 1[/sup]C(h[sub]i[/sub], h[sub]i + 1[/sub]) < M and [symbol]S[/symbol][sub]i = 1[/sub][sup]n[/sup]v(h[sub]i[/sub]) > k.[/li]
The traveling salesman problem is similar. An instance is a 3-tuple (H, C, M) with the following interpretation:[ul][li]H is the set of houses.[]C [symbol]Î[/symbol] H [symbol]´[/symbol] H [symbol]®[/symbol] Z[sup]+[/sup] is the cost function for moving from house to house.[]M is the maximum cost.[/ul]A solution to an instance of the traveling salesman problem is a sequence of houses h[sub]1[/sub], h[sub]2[/sub], …, h[sub]n[/sub] with [symbol]S[/symbol][sub]i = 1[/sub][sup]n - 1[/sup]C(h[sub]i[/sub], h[sub]i + 1[/sub]) < M.[/li]
Notice how similar the definitions are. That makes the reduction easy. Every instance of the traveling salesman problem (H, C, M) can be mapped onto an instance of the Halloween loot problem (H, C, v, M, |H|), where v(h) = 1 if house h has not been visited and 0 otherwise. H, C and M are inputs to the reduction, so they can be computed in constant time. v can be constructed in constant time, and |H| can be computed in linear time. Therefore, the reduction is polynomial, and we have that the Halloween loot problem is NP-hard.

But I promised to prove that it’s NP-complete, and to do that, I need to show that it’s in NP. This is easy. Verifying a solution simply involves n lookups into C, and n computations of v, for a total time that is [symbol]O/symbol. Therefore, the Halloween loot problem is verifiable in polynomial time, and is NP-complete.

Not to put down your hard work or anything but all you’ve proven is that if the halloween problem is NPC, then the TSP is NPC which is of no use whatsoever because we already know the TSP is NPC.

[ultrafilter]

@Shalmanese

Not to put down your hard work or anything but all you’ve proven is that if the halloween problem is NPC, then the TSP is NPC which is of no use whatsoever because we already know the TSP is NPC.

No I haven’t. To do that, I would’ve transformed an instance of the Halloween loot problem into an instance of the TSP. Read up on your reductions.

@Chronos

Except that distribution of houses (and hence, the distance function between them) usually follows some constraints that are not found in the general Travelling Salesman Problem. Namely, houses are distributed along streets, and the distance between two adjacent houses on the same street is less than the distance from a house to any of its nearest neighbors on on a different street. With these constraints, the problem becomes merely one of finding an Eulerian path on a graph (the vertices are intersections) with every edge doubled (since there are two sides to each street). And, of course, finding an Eulerian path on such a graph (or indeed, on any graph which has an Eulerian path) is child’s play.

Can you guarantee that the Eulerian path gives you the optimal candy take? It’s probably a very good approximation (and quite likely optimal for a small enough set of houses), I doubt that it will work in general.

[Trunk]

You need a good set of Baltimore row homes in a nice neighborhood.

Massive haul over minimal distance.

[Elendil_s_Heir]

@WhyNot

As a city-dweller, my advice is to get the hell outta Dodge… Halloween is still very American, and the rest of the world doesn’t get it - recent immigrants are likely to shut their curtains and ignore the goings-on…

NPR had a recent story on a Sri Lankan immigrant who moved to a nice section of Brooklyn in the late 1960s, and nearly had a heart attack when lots of strange, scary-looking short people rang her doorbell over and over for several hours one late October night.

Terrified, she never unlocked it…

[Elendil_s_Heir]

“It” being her door, of course. :smack: