事实证明，尽管没有针对非随机图的证据，但由于Angluin和Valiant（1977）而导致的汉密尔顿路径的局部搜索算法在此方面非常出色。这是一个样本广场
99 98 101 103 105 106 129 132 133 140 135 136
97 100 102 104 107 130 131 128 141 134 139 137
95 96 109 108 112 122 127 126 125 142 143 138
80 94 110 111 121 113 123 124 40 39 36 144
79 81 93 120 116 115 114 48 41 38 37 35
78 82 92 90 119 117 47 46 49 42 33 34
77 83 84 91 89 118 45 58 43 50 32 31
76 1 85 87 88 60 59 44 57 51 30 28
75 2 86 4 6 63 61 54 52 56 29 27
73 74 3 7 5 64 62 53 55 22 24 26
72 69 67 8 65 11 12 14 15 23 21 25
70 71 68 66 9 10 13 16 17 18 19 20
以及（有些草率编写的）Java代码。
import java.util.*;
public class AV {
public static void main(String[] args) {
// construct an n-by-n grid
int n = 12;
Node[][] node = new Node[n][n];
List<Node> nodes = new ArrayList<Node>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
nodes.add((node[i][j] = new Node()));
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i >= 1) {
if (j >= 1) {
node[i - 1][j - 1].addEdge(node[i][j]);
}
node[i - 1][j].addEdge(node[i][j]);
if (j < n - 1) {
node[i - 1][j + 1].addEdge(node[i][j]);
}
}
if (j >= 1) {
node[i][j - 1].addEdge(node[i][j]);
}
}
}
findPath(nodes);
labelPath(nodes);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.printf("%4d", node[i][j].label);
}
System.out.println();
}
}
private static void findPath(List<Node> nodes) {
for (Node node : nodes) {
node.isOnPath = false;
}
Random random = new Random();
Node sink = nodes.get(random.nextInt(nodes.size()));
sink.isOnPath = true;
int isNotOnPathCount = nodes.size() - 1;
while (isNotOnPathCount > 0) {
sink.pathOut = sink.out.get(random.nextInt(sink.out.size()));
sink = sink.pathOut.head;
if (sink.isOnPath) {
// rotate
sink = sink.pathOut.head;
Arc reverse = null;
Node node = sink;
do {
Arc temp = node.pathOut;
node.pathOut = reverse;
reverse = temp.reverse;
node = temp.head;
} while (node != sink);
} else {
// extend
sink.isOnPath = true;
isNotOnPathCount--;
}
}
}
private static void labelPath(Collection<Node> nodes) {
for (Node node : nodes) {
node.isSource = true;
}
for (Node node : nodes) {
if (node.pathOut != null) {
node.pathOut.head.isSource = false;
}
}
Node source = null;
for (Node node : nodes) {
if (node.isSource) {
source = node;
break;
}
}
int count = 0;
while (true) {
source.label = ++count;
if (source.pathOut == null) {
break;
}
source = source.pathOut.head;
}
}
}
class Node {
public final List<Arc> out = new ArrayList<Arc>();
public boolean isOnPath;
public Arc pathOut;
public boolean isSource;
public int label;
public void addEdge(Node that) {
Arc arc = new Arc(this, that);
this.out.add(arc.reverse);
that.out.add(arc);
}
}
class Arc {
public final Node head;
public final Arc reverse;
private Arc(Node head, Arc reverse) {
this.head = head;
this.reverse = reverse;
}
public Arc(Node head, Node tail) {
this.head = head;
this.reverse = new Arc(tail, this);
}
}
602392714
清零编程群