逻辑引擎

简单回合制游戏

对于不能简单画出由游戏局面所构成的状态空间时，还有以下分析策略可用：

一种局面，是否先手必胜，取决于先手是否可以经过一步操作就将该局面变为后手必胜局面。如果先手对该局面的每一种可能的单步操作都无法将局面变为后手必胜局面，那么该局面就是后手必胜局面。

在通过倒推的方法分析回合制游戏必胜策略的时候，凡是后手必胜策略的局面，所有可以通过一步操作就到达该局面的局面都是先手有必胜策略的局面。而寻找后手有必胜策略的局面就比较困难，只有那些所有选择都导致下一步先手必胜的局面才是后手有必胜策略的局面。

August 5th, 2011 | 荒唐 | Categories: 数学, 算法 | Comments: No Comments

Reinvent wheels, my quick sort implementation, just for fun

Not deeply optimized.
The depth of the recursion is restricted $\le log_2(N)$ , because the recursion is only performed for the partition with less element. Even under the worst case, the stack depth will still be under control.
Tail recursion is eliminated.

Brief explanation:
[cc lang=”cpp”]
initial state:
p<<< # p=== # | p>>>
p… |
|—————————————–|
……………………………………#

state after choosing the pivot:
p<<< # p=== # | p>>>
|p… |
||—————————————-|
=…………………………………..#

the middle state during partitioning:
p<<< # | p=== # | | p>>> #
| | p… | #
|——–|———|—————-|—–#
<<<<<<<<<==========.................>>>>>>#

the final state after partition:
p<<< # | p=== # | | p>>> #
| | p… #
|—————|—————|———#
<<<<<<<<<<<<<<<<================>>>>>>>>>>#

Then, recurse.
[/cc]
Pointer “p<<<" points to the begining of the "<<<" area in which each element is preceding to the pivot. Pointer "p===" points to the begining of the "===" area in which each element is equivalent to the pivot. Pointer "p>>>” points to the begining of the “>>>” area in which each element is succeeding to the pivot.
Pointer “p…” points to the begining of the “…” area in which each element is unprocessed.

The code:
[cc lang=”cpp”]
template
class QuickSort {
public:
static void sort(Elem pp[], size_t n) {
Elem *pe, *pu, *ps;
// pp:”p<<<", pe:"p===", ps:"p>>>”, pu:”p…”
do {
// recursion exit, use other sort algorithm to process small array
// recommendation: use sorting network algorithm when array size less than 9
if(n < Cutoff) { ShortSort::sort(pp, n);
return;
}

pe = pp;
pu = pp;
ps = pp+n;

// choosing pivot
swap(pe, pivot(pp, n));
pu++;

// partitioning
while(pu < ps) { while((*pe == *pu) && (pu < ps)) ++pu; while((*pe < *pu) && (pu < ps)) { --ps; swap(pu, ps); } while((*pu < *pe) && (pu < ps)) { swap(pe, pu); ++pe; ++pu; } } // recursion only for the partition with less elements if((pe - pp) < (n - (ps - pp))) { sort(pp, pe - pp); n = n - (ps - pp); pp = ps; } else { sort(ps, n - (ps - pp)); n = pe - pp; } // tail recursion elimination } while(true); } private: static Elem *pivot(Elem pp[], size_t n) { if(n < 10) return pp + n/2; else return pp + random(n); // random(n) should return a uniformly distributed random number in [0, n) } }; [/cc]

January 18th, 2011 | 荒唐 | Categories: 算法 | Comments: No Comments

Finding all paths from source to destination

[cc lang=”cpp”]
stack node_stack;
set node_set;
AllPathFromSourceToDestination(node s, node d) {
node_stack.push(s);
node_set.add(s); //mark each node in the path
// for each node v that adjacent with node s:
for_each(node v, adjacent(v,s)) {
if(v == d) {
Output(node_stack);
} else {
if(node_set.has(v)==false) {
AllPathFromSourceToDestination(v, d);
}
}
}
node_set.del(s);
node_stack.pop(s);
}
[/cc]

January 18th, 2011 | 荒唐 | Categories: 数学, 算法 | Comments: No Comments

Sorting network

The following is network-sorting algorithm for less than 33 elements.

What is Sorting Network? Wiki: sorting network

List of sorting networks:
From: sorting networks
Input the number n (maximum 32)
Algorithm choices: “Best”
Click [Take a look] button.

—————————
Zero-one principle

While it is easy to prove the validity of some sorting networks (like the insertion/bubble sorter), it is not always so easy. There are n! permutations of numbers in an n-wire network, and to test all of them would take a significant amount of time, especially when they are larger. However, because of the so-called zero-one principle, far fewer trials are in fact needed to test the validity of a sorting network.

The zero-one principle states that a sorting network is valid if it can sort all 2n sequences of 0s and 1s. This not only drastically cuts down on the number of tests needed to ascertain the validity of a network, it is of great use in creating many constructions of sorting networks as well. The principle has been proven by a special case of the Bouricius’s Theorem in 1954 by W. G. Bouricius.

[cc lang=”cpp”]
static const unsigned int network02[][2] = {
{ 0, 1},
};
static const unsigned int network03[][2] = {
{ 1, 2},
{ 0, 2},
{ 0, 1},
};
static const unsigned int network04[][2] = {
{ 0, 1}, { 2, 3},
{ 0, 2}, { 1, 3},
{ 1, 2},
};
static const unsigned int network05[][2] = {
{ 0, 1}, { 3, 4},
{ 2, 4},
{ 2, 3}, { 1, 4},
{ 0, 3},
{ 0, 2}, { 1, 3},
{ 1, 2},
};
static const unsigned int network06[][2] = {
{ 1, 2}, { 4, 5},
{ 0, 2}, { 3, 5},
{ 0, 1}, { 3, 4}, { 2, 5},
{ 0, 3}, { 1, 4},
{ 2, 4}, { 1, 3},
{ 2, 3},
};
static const unsigned int network07[][2] = {
{ 1, 2}, { 3, 4}, { 5, 6},
{ 0, 2}, { 3, 5}, { 4, 6},
{ 0, 1}, { 4, 5}, { 2, 6},
{ 0, 4}, { 1, 5},
{ 0, 3}, { 2, 5},
{ 1, 3}, { 2, 4},
{ 2, 3},
};
static const unsigned int network08[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7},
{ 0, 2}, { 1, 3}, { 4, 6}, { 5, 7},
{ 1, 2}, { 5, 6}, { 0, 4}, { 3, 7},
{ 1, 5}, { 2, 6},
{ 1, 4}, { 3, 6},
{ 2, 4}, { 3, 5},
{ 3, 4},
};
static const unsigned int network09[][2] = {
{ 0, 1}, { 3, 4}, { 6, 7},
{ 1, 2}, { 4, 5}, { 7, 8},
{ 0, 1}, { 3, 4}, { 6, 7}, { 2, 5},
{ 0, 3}, { 1, 4}, { 5, 8},
{ 3, 6}, { 4, 7}, { 2, 5},
{ 0, 3}, { 1, 4}, { 5, 7}, { 2, 6},
{ 1, 3}, { 4, 6},
{ 2, 4}, { 5, 6},
{ 2, 3},
};
static const unsigned int network10[][2] = {
{ 4, 9}, { 3, 8}, { 2, 7}, { 1, 6}, { 0, 5},
{ 1, 4}, { 6, 9}, { 0, 3}, { 5, 8},
{ 0, 2}, { 3, 6}, { 7, 9},
{ 0, 1}, { 2, 4}, { 5, 7}, { 8, 9},
{ 1, 2}, { 4, 6}, { 7, 8}, { 3, 5},
{ 2, 5}, { 6, 8}, { 1, 3}, { 4, 7},
{ 2, 3}, { 6, 7},
{ 3, 4}, { 5, 6},
{ 4, 5},
};
static const unsigned int network11[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9},
{ 1, 3}, { 5, 7}, { 0, 2}, { 4, 6}, { 8,10},
{ 1, 2}, { 5, 6}, { 9,10}, { 0, 4}, { 3, 7},
{ 1, 5}, { 6,10}, { 4, 8},
{ 5, 9}, { 2, 6}, { 0, 4}, { 3, 8},
{ 1, 5}, { 6,10}, { 2, 3}, { 8, 9},
{ 1, 4}, { 7,10}, { 3, 5}, { 6, 8},
{ 2, 4}, { 7, 9}, { 5, 6},
{ 3, 4}, { 7, 8},
};
static const unsigned int network12[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11},
{ 1, 3}, { 5, 7}, { 9,11}, { 0, 2}, { 4, 6}, { 8,10},
{ 1, 2}, { 5, 6}, { 9,10}, { 0, 4}, { 7,11},
{ 1, 5}, { 6,10}, { 3, 7}, { 4, 8},
{ 5, 9}, { 2, 6}, { 0, 4}, { 7,11}, { 3, 8},
{ 1, 5}, { 6,10}, { 2, 3}, { 8, 9},
{ 1, 4}, { 7,10}, { 3, 5}, { 6, 8},
{ 2, 4}, { 7, 9}, { 5, 6},
{ 3, 4}, { 7, 8},
};
static const unsigned int network13[][2] = {
{ 1, 7}, { 9,11}, { 3, 4}, { 5, 8}, { 0,12}, { 2, 6},
{ 0, 1}, { 2, 3}, { 4, 6}, { 8,11}, { 7,12}, { 5, 9},
{ 0, 2}, { 3, 7}, {10,11}, { 1, 4}, { 6,12},
{ 7, 8}, {11,12}, { 4, 9}, { 6,10},
{ 3, 4}, { 5, 6}, { 8, 9}, {10,11}, { 1, 7},
{ 2, 6}, { 9,11}, { 1, 3}, { 4, 7}, { 8,10}, { 0, 5},
{ 2, 5}, { 6, 8}, { 9,10},
{ 1, 2}, { 3, 5}, { 7, 8}, { 4, 6},
{ 2, 3}, { 4, 5}, { 6, 7}, { 8, 9},
{ 3, 4}, { 5, 6},
};
static const unsigned int network14[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11}, {12,13},
{ 0, 2}, { 4, 6}, { 8,10}, { 1, 3}, { 5, 7}, { 9,11},
{ 0, 4}, { 8,12}, { 1, 5}, { 9,13}, { 2, 6}, { 3, 7},
{ 0, 8}, { 1, 9}, { 2,10}, { 3,11}, { 4,12}, { 5,13},
{ 5,10}, { 6, 9}, { 3,12}, { 7,11}, { 1, 2}, { 4, 8},
{ 1, 4}, { 7,13}, { 2, 8}, { 5, 6}, { 9,10},
{ 2, 4}, {11,13}, { 3, 8}, { 7,12},
{ 6, 8}, {10,12}, { 3, 5}, { 7, 9},
{ 3, 4}, { 5, 6}, { 7, 8}, { 9,10}, {11,12},
{ 6, 7}, { 8, 9},
};
static const unsigned int network15[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11}, {12,13},
{ 0, 2}, { 4, 6}, { 8,10}, {12,14}, { 1, 3}, { 5, 7}, { 9,11},
{ 0, 4}, { 8,12}, { 1, 5}, { 9,13}, { 2, 6}, {10,14}, { 3, 7},
{ 0, 8}, { 1, 9}, { 2,10}, { 3,11}, { 4,12}, { 5,13}, { 6,14},
{ 5,10}, { 6, 9}, { 3,12}, {13,14}, { 7,11}, { 1, 2}, { 4, 8},
{ 1, 4}, { 7,13}, { 2, 8}, {11,14}, { 5, 6}, { 9,10},
{ 2, 4}, {11,13}, { 3, 8}, { 7,12},
{ 6, 8}, {10,12}, { 3, 5}, { 7, 9},
{ 3, 4}, { 5, 6}, { 7, 8}, { 9,10}, {11,12},
{ 6, 7}, { 8, 9},
};
static const unsigned int network16[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11}, {12,13}, {14,15},
{ 0, 2}, { 4, 6}, { 8,10}, {12,14}, { 1, 3}, { 5, 7}, { 9,11}, {13,15},
{ 0, 4}, { 8,12}, { 1, 5}, { 9,13}, { 2, 6}, {10,14}, { 3, 7}, {11,15},
{ 0, 8}, { 1, 9}, { 2,10}, { 3,11}, { 4,12}, { 5,13}, { 6,14}, { 7,15},
{ 5,10}, { 6, 9}, { 3,12}, {13,14}, { 7,11}, { 1, 2}, { 4, 8},
{ 1, 4}, { 7,13}, { 2, 8}, {11,14}, { 5, 6}, { 9,10},
{ 2, 4}, {11,13}, { 3, 8}, { 7,12},
{ 6, 8}, {10,12}, { 3, 5}, { 7, 9},
{ 3, 4}, { 5, 6}, { 7, 8}, { 9,10}, {11,12},
{ 6, 7}, { 8, 9},
};
static const unsigned int network17[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11}, {12,13}, {15,16},
{ 0, 2}, { 1, 3}, { 4, 6}, { 5, 7}, { 8,10}, { 9,11}, {14,16},
{ 1, 2}, { 5, 6}, { 0, 4}, { 3, 7}, { 9,10}, {14,15}, {13,16},
{ 1, 5}, { 2, 6}, {12,15}, {11,16},
{ 1, 4}, { 3, 6}, {12,14}, {13,15}, { 7,16},
{ 2, 4}, { 3, 5}, {13,14}, {10,15},
{ 3, 4}, { 8,13}, { 9,14}, {11,15},
{ 8,12}, { 9,13}, {11,14}, { 6,15},
{ 9,12}, {10,13}, { 5,14}, { 7,15},
{10,12}, {11,13}, { 0, 9}, { 7,14},
{11,12}, { 0, 8}, { 1,10}, { 4,13},
{ 1, 9}, { 2,11}, { 3,12}, { 5,13},
{ 1, 8}, { 3,11}, { 2, 9}, { 6,13},
{ 2, 8}, { 3,10}, { 7,13}, { 6,11},
{ 3, 9}, { 5,10}, { 7,12},
{ 3, 8}, { 4, 9}, { 7,11},
{ 4, 8}, { 5, 9}, { 7,10},
{ 5, 8}, { 6, 9},
{ 6, 8}, { 7, 9},
{ 7, 8},
};
static const unsigned int network18[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 7, 8}, { 9,10}, {11,12}, {13,14}, {16,17},
{ 0, 2}, { 1, 3}, { 6, 8}, { 9,11}, {10,12}, {15,17},
{ 1, 2}, { 6, 7}, { 5, 8}, {10,11}, {15,16}, {14,17},
{ 4, 7}, { 3, 8}, {13,16}, {12,17},
{ 4, 6}, { 5, 7}, {13,15}, {14,16}, { 8,17},
{ 5, 6}, { 2, 7}, {14,15}, {11,16},
{ 0, 5}, { 1, 6}, { 3, 7}, { 9,14}, {10,15}, {12,16},
{ 0, 4}, { 1, 5}, { 3, 6}, { 9,13}, {10,14}, {12,15}, { 7,16},
{ 1, 4}, { 2, 5}, {10,13}, {11,14}, { 0, 9}, { 6,15}, { 8,16},
{ 2, 4}, { 3, 5}, {11,13}, {12,14}, { 1,10}, { 7,15},
{ 3, 4}, {12,13}, { 1, 9}, { 2,11}, { 5,14}, { 8,15},
{ 3,12}, { 2, 9}, { 4,13}, { 7,14},
{ 3,11}, { 5,13}, { 8,14},
{ 3,10}, { 6,13},
{ 3, 9}, { 7,13}, { 5,10}, { 6,11},
{ 8,13}, { 4, 9}, { 7,12},
{ 5, 9}, { 8,12}, { 7,11},
{ 8,11}, { 6, 9}, { 7,10},
{ 8,10}, { 7, 9},
{ 8, 9},
};
static const unsigned int network19[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 7, 8}, { 9,10}, {12,13}, {14,15}, {17,18},
{ 0, 2}, { 1, 3}, { 6, 8}, {11,13}, {16,18},
{ 1, 2}, { 6, 7}, { 5, 8}, {11,12}, {10,13}, {16,17}, {15,18},
{ 4, 7}, { 3, 8}, { 9,12}, {14,17}, {13,18},
{ 4, 6}, { 5, 7}, { 9,11}, {10,12}, {14,16}, {15,17}, { 8,18},
{ 5, 6}, { 2, 7}, {10,11}, {15,16}, { 9,14}, {12,17},
{ 0, 5}, { 1, 6}, { 3, 7}, {10,15}, {11,16}, {13,17},
{ 0, 4}, { 1, 5}, { 3, 6}, {10,14}, {12,16}, { 7,17},
{ 1, 4}, { 2, 5}, {13,16}, {11,14}, {12,15}, { 0,10}, { 8,17},
{ 2, 4}, { 3, 5}, {13,15}, {12,14}, { 0, 9}, { 1,11}, { 6,16},
{ 3, 4}, {13,14}, { 1,10}, { 2,12}, { 5,15}, { 7,16},
{ 1, 9}, { 3,13}, { 2,10}, { 4,14}, { 8,16}, { 7,15},
{ 3,12}, { 2, 9}, { 5,14}, { 8,15},
{ 3,11}, { 6,14},
{ 3,10}, { 7,14}, { 6,11},
{ 3, 9}, { 8,14}, { 5,10}, { 7,12},
{ 4, 9}, { 8,13}, { 7,11},
{ 5, 9}, { 8,12}, { 7,10},
{ 8,11}, { 6, 9},
{ 8,10}, { 7, 9},
{ 8, 9},
};
static const unsigned int network20[][2] = {
{ 0, 1}, { 3, 4}, { 5, 6}, { 8, 9}, {10,11}, {13,14}, {15,16}, {18,19},
{ 2, 4}, { 7, 9}, {12,14}, {17,19},
{ 2, 3}, { 1, 4}, { 7, 8}, { 6, 9}, {12,13}, {11,14}, {17,18}, {16,19},
{ 0, 3}, { 5, 8}, { 4, 9}, {10,13}, {15,18}, {14,19},
{ 0, 2}, { 1, 3}, { 5, 7}, { 6, 8}, {10,12}, {11,13}, {15,17}, {16,18}, { 9,19},
{ 1, 2}, { 6, 7}, { 0, 5}, { 3, 8}, {11,12}, {16,17}, {10,15}, {13,18},
{ 1, 6}, { 2, 7}, { 4, 8}, {11,16}, {12,17}, {14,18}, { 0,10},
{ 1, 5}, { 3, 7}, {11,15}, {13,17}, { 8,18},
{ 4, 7}, { 2, 5}, { 3, 6}, {14,17}, {12,15}, {13,16}, { 1,11}, { 9,18},
{ 4, 6}, { 3, 5}, {14,16}, {13,15}, { 1,10}, { 2,12}, { 7,17},
{ 4, 5}, {14,15}, { 3,13}, { 2,10}, { 6,16}, { 8,17},
{ 4,14}, { 3,12}, { 5,15}, { 9,17}, { 8,16},
{ 4,13}, { 3,11}, { 6,15}, { 9,16},
{ 4,12}, { 3,10}, { 7,15},
{ 4,11}, { 8,15}, { 7,12},
{ 4,10}, { 9,15}, { 6,11}, { 8,13},
{ 5,10}, { 9,14}, { 8,12},
{ 6,10}, { 9,13}, { 8,11},
{ 9,12}, { 7,10},
{ 9,11}, { 8,10},
{ 9,10},
};
static const unsigned int network21[][2] = {
{ 0, 1}, { 3, 4}, { 5, 6}, { 8, 9}, {10,11}, {13,14}, {16,17}, {19,20},
{ 2, 4}, { 7, 9}, {12,14}, {15,17}, {18,20},
{ 2, 3}, { 1, 4}, { 7, 8}, { 6, 9}, {12,13}, {11,14}, {15,16}, {18,19}, {17,20},
{ 0, 3}, { 5, 8}, { 4, 9}, {10,13}, {15,18}, {16,19}, {14,20},
{ 0, 2}, { 1, 3}, { 5, 7}, { 6, 8}, {10,12}, {11,13}, {17,19}, {16,18}, { 9,20},
{ 1, 2}, { 6, 7}, { 0, 5}, { 3, 8}, {11,12}, {17,18}, {10,16}, {13,19},
{ 1, 6}, { 2, 7}, { 4, 8}, {10,15}, {11,17}, {12,18}, {14,19},
{ 1, 5}, { 3, 7}, {11,16}, {13,18}, { 8,19},
{ 4, 7}, { 2, 5}, { 3, 6}, {11,15}, {14,18}, {13,16}, { 9,19},
{ 4, 6}, { 3, 5}, {12,15}, {14,17}, { 0,11}, { 7,18},
{ 4, 5}, {14,16}, {13,15}, { 0,10}, { 1,12}, { 6,17}, { 8,18},
{14,15}, { 1,11}, { 2,13}, { 5,16}, { 9,18}, { 8,17},
{ 1,10}, { 3,14}, { 4,15}, { 6,16}, { 9,17},
{ 4,14}, { 3,13}, { 2,10}, { 7,16},
{ 4,13}, { 3,11}, { 8,16},
{ 4,12}, { 3,10}, { 9,16}, { 7,13}, { 8,14},
{ 4,11}, { 6,12}, { 9,15}, { 8,13},
{ 4,10}, { 5,11}, { 9,14},
{ 5,10}, { 6,11}, { 9,13},
{ 6,10}, { 8,11}, { 9,12},
{ 7,10}, { 9,11},
{ 8,10},
{ 9,10},
};
static const unsigned int network22[][2] = {
{ 0, 1}, { 3, 4}, { 6, 7}, { 9,10}, {11,12}, {14,15}, {17,18}, {20,21},
{ 2, 4}, { 5, 7}, { 8,10}, {13,15}, {16,18}, {19,21},
{ 2, 3}, { 1, 4}, { 5, 6}, { 8, 9}, { 7,10}, {13,14}, {12,15}, {16,17}, {19,20}, {18,21},
{ 0, 3}, { 5, 8}, { 6, 9}, { 4,10}, {11,14}, {16,19}, {17,20}, {15,21},
{ 0, 2}, { 1, 3}, { 7, 9}, { 6, 8}, {11,13}, {12,14}, {18,20}, {17,19}, {10,21},
{ 1, 2}, { 7, 8}, { 0, 6}, { 3, 9}, {12,13}, {18,19}, {11,17}, {14,20},
{ 0, 5}, { 1, 7}, { 2, 8}, { 4, 9}, {11,16}, {12,18}, {13,19}, {15,20},
{ 1, 6}, { 3, 8}, {12,17}, {14,19}, { 0,11}, { 9,20},
{ 1, 5}, { 4, 8}, { 3, 6}, {12,16}, {15,19}, {14,17}, {10,20},
{ 2, 5}, { 4, 7}, {13,16}, {15,18}, { 1,12}, { 8,19},
{ 4, 6}, { 3, 5}, {15,17}, {14,16}, { 1,11}, { 2,13}, { 7,18}, { 9,19},
{ 4, 5}, {15,16}, { 3,14}, { 2,11}, { 6,17}, {10,19},
{ 4,15}, { 3,13}, { 5,16}, { 7,17}, {10,18},
{ 4,14}, { 3,12}, { 6,16}, { 9,17},
{ 4,13}, { 3,11}, { 7,16}, {10,17},
{ 4,12}, { 8,16}, { 7,13},
{ 4,11}, { 9,16}, { 6,12}, { 8,14},
{10,16}, { 5,11}, { 7,12}, { 9,15},
{ 6,11}, {10,15}, { 9,14},
{ 7,11}, {10,14}, { 9,12},
{ 8,11}, {10,13},
{10,12}, { 9,11},
{10,11},
};
static const unsigned int network23[][2] = {
{ 0, 1}, { 3, 4}, { 6, 7}, { 9,10}, {12,13}, {15,16}, {18,19}, {21,22},
{ 2, 4}, { 5, 7}, { 8,10}, {11,13}, {14,16}, {17,19}, {20,22},
{ 2, 3}, { 1, 4}, { 5, 6}, { 8, 9}, { 7,10}, {11,12}, {14,15}, {13,16}, {17,18}, {20,21}, {19,22},
{ 0, 3}, { 5, 8}, { 6, 9}, { 4,10}, {11,14}, {12,15}, {17,20}, {18,21}, {16,22},
{ 0, 2}, { 1, 3}, { 7, 9}, { 6, 8}, {13,15}, {12,14}, {19,21}, {18,20}, {11,17}, {10,22},
{ 1, 2}, { 7, 8}, { 0, 6}, { 3, 9}, {13,14}, {19,20}, {12,18}, {15,21},
{ 0, 5}, { 1, 7}, { 2, 8}, { 4, 9}, {13,19}, {12,17}, {14,20}, {16,21},
{ 1, 6}, { 3, 8}, {13,18}, {15,20}, { 0,12}, { 9,21},
{ 1, 5}, { 4, 8}, { 3, 6}, {13,17}, {16,20}, {15,18}, { 0,11}, {10,21},
{ 2, 5}, { 4, 7}, {14,17}, {16,19}, { 1,13}, { 8,20},
{ 4, 6}, { 3, 5}, {16,18}, {15,17}, { 1,12}, { 2,14}, { 7,19}, { 9,20},
{ 4, 5}, {16,17}, { 1,11}, { 3,15}, { 6,18}, {10,20},
{ 4,16}, { 3,14}, { 2,11}, { 5,17}, { 7,18}, {10,19},
{ 4,15}, { 3,12}, { 6,17}, { 9,18},
{ 4,14}, { 3,11}, { 7,17}, {10,18},
{ 4,13}, { 8,17},
{ 4,12}, { 9,17}, { 7,13}, { 8,14},
{ 4,11}, {10,17}, { 6,12}, { 9,15},
{ 5,11}, { 7,12}, {10,16}, { 9,14},
{ 6,11}, {10,15}, { 9,12},
{ 7,11}, {10,14},
{ 8,11}, {10,13},
{10,12}, { 9,11},
{10,11},
};
static const unsigned int network24[][2] = {
{ 1, 2}, { 4, 5}, { 7, 8}, {10,11}, {13,14}, {16,17}, {19,20}, {22,23},
{ 0, 2}, { 3, 5}, { 6, 8}, { 9,11}, {12,14}, {15,17}, {18,20}, {21,23},
{ 0, 1}, { 3, 4}, { 2, 5}, { 6, 7}, { 9,10}, { 8,11}, {12,13}, {15,16}, {14,17}, {18,19}, {21,22}, {20,23},
{ 0, 3}, { 1, 4}, { 6, 9}, { 7,10}, { 5,11}, {12,15}, {13,16}, {18,21}, {19,22}, {17,23},
{ 2, 4}, { 1, 3}, { 8,10}, { 7, 9}, { 0, 6}, {14,16}, {13,15}, {20,22}, {19,21}, {12,18}, {11,23},
{ 2, 3}, { 8, 9}, { 1, 7}, { 4,10}, {14,15}, {20,21}, {13,19}, {16,22}, { 0,12},
{ 2, 8}, { 1, 6}, { 3, 9}, { 5,10}, {14,20}, {13,18}, {15,21}, {17,22},
{ 2, 7}, { 4, 9}, {14,19}, {16,21}, { 1,13}, {10,22},
{ 2, 6}, { 5, 9}, { 4, 7}, {14,18}, {17,21}, {16,19}, { 1,12}, {11,22},
{ 3, 6}, { 5, 8}, {15,18}, {17,20}, { 2,14}, { 9,21},
{ 5, 7}, { 4, 6}, {17,19}, {16,18}, { 2,13}, { 3,15}, { 8,20}, {10,21},
{ 5, 6}, {17,18}, { 2,12}, { 4,16}, { 7,19}, {11,21},
{ 5,17}, { 4,15}, { 3,12}, { 6,18}, { 8,19}, {11,20},
{ 5,16}, { 4,13}, { 7,18}, {10,19},
{ 5,15}, { 4,12}, { 8,18}, {11,19},
{ 5,14}, { 9,18},
{ 5,13}, {10,18}, { 8,14}, { 9,15},
{ 5,12}, {11,18}, { 7,13}, {10,16},
{ 6,12}, { 8,13}, {11,17}, {10,15},
{ 7,12}, {11,16}, {10,13},
{ 8,12}, {11,15},
{ 9,12}, {11,14},
{11,13}, {10,12},
{11,12},
};
static const unsigned int network25[][2] = {
{ 1, 2}, { 4, 5}, { 7, 8}, {10,11}, {13,14}, {16,17}, {19,20}, {21,22}, {23,24},
{ 0, 2}, { 3, 5}, { 6, 8}, { 9,11}, {12,14}, {15,17}, {18,20}, {21,23}, {22,24},
{ 0, 1}, { 3, 4}, { 2, 5}, { 6, 7}, { 9,10}, { 8,11}, {12,13}, {15,16}, {14,17}, {18,19}, {22,23}, {20,24},
{ 0, 3}, { 1, 4}, { 6, 9}, { 7,10}, { 5,11}, {12,15}, {13,16}, {18,22}, {19,23}, {17,24},
{ 2, 4}, { 1, 3}, { 8,10}, { 7, 9}, { 0, 6}, {14,16}, {13,15}, {18,21}, {20,23}, {11,24},
{ 2, 3}, { 8, 9}, { 1, 7}, { 4,10}, {14,15}, {19,21}, {20,22}, {16,23},
{ 2, 8}, { 1, 6}, { 3, 9}, { 5,10}, {20,21}, {12,19}, {15,22}, {17,23},
{ 2, 7}, { 4, 9}, {12,18}, {13,20}, {14,21}, {16,22}, {10,23},
{ 2, 6}, { 5, 9}, { 4, 7}, {14,20}, {13,18}, {17,22}, {11,23},
{ 3, 6}, { 5, 8}, {14,19}, {16,20}, {17,21}, { 0,13}, { 9,22},
{ 5, 7}, { 4, 6}, {14,18}, {15,19}, {17,20}, { 0,12}, { 8,21}, {10,22},
{ 5, 6}, {15,18}, {17,19}, { 1,14}, { 7,20}, {11,22},
{16,18}, { 2,15}, { 1,12}, { 6,19}, { 8,20}, {11,21},
{17,18}, { 2,14}, { 3,16}, { 7,19}, {10,20},
{ 2,13}, { 4,17}, { 5,18}, { 8,19}, {11,20},
{ 2,12}, { 5,17}, { 4,16}, { 3,13}, { 9,19},
{ 5,16}, { 3,12}, { 4,14}, {10,19},
{ 5,15}, { 4,12}, {11,19}, { 9,16}, {10,17},
{ 5,14}, { 8,15}, {11,18}, {10,16},
{ 5,13}, { 7,14}, {11,17},
{ 5,12}, { 6,13}, { 8,14}, {11,16},
{ 6,12}, { 8,13}, {10,14}, {11,15},
{ 7,12}, { 9,13}, {11,14},
{ 8,12}, {11,13},
{ 9,12},
{10,12},
{11,12},
};
static const unsigned int network26[][2] = {
{ 1, 2}, { 4, 5}, { 7, 8}, { 9,10}, {11,12}, {14,15}, {17,18}, {20,21}, {22,23}, {24,25},
{ 0, 2}, { 3, 5}, { 6, 8}, { 9,11}, {10,12}, {13,15}, {16,18}, {19,21}, {22,24}, {23,25},
{ 0, 1}, { 3, 4}, { 2, 5}, { 6, 7}, {10,11}, { 8,12}, {13,14}, {16,17}, {15,18}, {19,20}, {23,24}, {21,25},
{ 0, 3}, { 1, 4}, { 6,10}, { 7,11}, { 5,12}, {13,16}, {14,17}, {19,23}, {20,24}, {18,25},
{ 2, 4}, { 1, 3}, { 6, 9}, { 8,11}, {15,17}, {14,16}, {19,22}, {21,24}, {12,25},
{ 2, 3}, { 7, 9}, { 8,10}, { 4,11}, {15,16}, {20,22}, {21,23}, {17,24},
{ 8, 9}, { 0, 7}, { 3,10}, { 5,11}, {21,22}, {13,20}, {16,23}, {18,24},
{ 0, 6}, { 1, 8}, { 2, 9}, { 4,10}, {13,19}, {14,21}, {15,22}, {17,23}, {11,24},
{ 2, 8}, { 1, 6}, { 5,10}, {15,21}, {14,19}, {18,23}, { 0,13}, {12,24},
{ 2, 7}, { 4, 8}, { 5, 9}, {15,20}, {17,21}, {18,22}, { 1,14}, {10,23},
{ 2, 6}, { 3, 7}, { 5, 8}, {15,19}, {16,20}, {18,21}, { 1,13}, { 9,22}, {12,23},
{ 3, 6}, { 5, 7}, {16,19}, {18,20}, { 2,15}, { 8,21}, {10,22},
{ 4, 6}, {17,19}, { 2,14}, { 3,16}, { 7,20}, {11,22},
{ 5, 6}, {18,19}, { 2,13}, { 4,17}, { 8,20}, {12,22}, {11,21},
{ 5,18}, { 4,16}, { 3,13}, { 6,19}, {10,20}, {12,21},
{ 5,17}, { 4,14}, { 7,19}, {12,20},
{ 5,16}, { 4,13}, { 8,19},
{ 5,15}, { 9,19},
{ 5,14}, {10,19}, { 8,15}, { 9,16},
{ 5,13}, {11,19}, { 7,14}, {10,17},
{12,19}, { 6,13}, { 8,14}, {10,16}, {11,18},
{ 7,13}, {12,18}, {11,16}, {10,14},
{ 8,13}, {12,17}, {11,15},
{12,16}, { 9,13},
{10,13}, {12,15},
{11,13}, {12,14},
{12,13},
};
static const unsigned int network27[][2] = {
{ 1, 2}, { 4, 5}, { 7, 8}, { 9,10}, {11,12}, {14,15}, {16,17}, {18,19}, {21,22}, {23,24}, {25,26},
{ 0, 2}, { 3, 5}, { 6, 8}, { 9,11}, {10,12}, {13,15}, {16,18}, {17,19}, {20,22}, {23,25}, {24,26},
{ 0, 1}, { 3, 4}, { 2, 5}, { 6, 7}, {10,11}, { 8,12}, {13,14}, {17,18}, {15,19}, {20,21}, {24,25}, {22,26},
{ 0, 3}, { 1, 4}, { 6,10}, { 7,11}, { 5,12}, {13,17}, {14,18}, {20,24}, {21,25}, {19,26},
{ 2, 4}, { 1, 3}, { 6, 9}, { 8,11}, {13,16}, {15,18}, {20,23}, {22,25}, {12,26},
{ 2, 3}, { 7, 9}, { 8,10}, { 4,11}, {14,16}, {15,17}, {21,23}, {22,24}, {13,20}, {18,25},
{ 8, 9}, { 0, 7}, { 3,10}, { 5,11}, {15,16}, {22,23}, {14,21}, {17,24}, {19,25},
{ 0, 6}, { 1, 8}, { 2, 9}, { 4,10}, {15,22}, {14,20}, {16,23}, {19,24}, {11,25},
{ 2, 8}, { 1, 6}, { 5,10}, {15,21}, {17,23}, { 0,14}, {12,25},
{ 2, 7}, { 4, 8}, { 5, 9}, {15,20}, {18,23}, {17,21}, { 0,13}, {10,24},
{ 2, 6}, { 3, 7}, { 5, 8}, {19,23}, {16,20}, {18,22}, { 1,15}, {12,24},
{ 3, 6}, { 5, 7}, {17,20}, {19,22}, { 2,16}, { 1,13}, { 9,23},
{ 4, 6}, {18,20}, {19,21}, { 2,15}, { 3,17}, { 8,22}, {10,23},
{ 5, 6}, {19,20}, { 2,14}, { 4,18}, { 7,21}, {11,23},
{ 2,13}, { 5,19}, { 4,17}, { 3,14}, { 6,20}, { 8,21}, {12,23}, {11,22},
{ 5,18}, { 3,13}, { 4,15}, { 7,20}, {10,21}, {12,22},
{ 5,17}, { 4,13}, { 8,20}, {12,21},
{ 5,16}, { 9,20},
{ 5,15}, {10,20}, { 9,16},
{ 5,14}, {11,20}, { 8,15}, {10,17},
{ 5,13}, {12,20}, { 7,14}, {10,16}, {11,18},
{ 6,13}, { 8,14}, {12,19}, {11,16},
{ 7,13}, {12,18}, {10,14}, {11,15},
{ 8,13}, {12,17},
{12,16}, { 9,13},
{10,13}, {12,15},
{11,13}, {12,14},
{12,13},
};
static const unsigned int network28[][2] = {
{ 1, 2}, { 3, 4}, { 5, 6}, { 8, 9}, {10,11}, {12,13}, {15,16}, {17,18}, {19,20}, {22,23}, {24,25}, {26,27},
{ 0, 2}, { 3, 5}, { 4, 6}, { 7, 9}, {10,12}, {11,13}, {14,16}, {17,19}, {18,20}, {21,23}, {24,26}, {25,27},
{ 0, 1}, { 4, 5}, { 2, 6}, { 7, 8}, {11,12}, { 9,13}, {14,15}, {18,19}, {16,20}, {21,22}, {25,26}, {23,27},
{ 0, 4}, { 1, 5}, { 7,11}, { 8,12}, { 6,13}, {14,18}, {15,19}, {21,25}, {22,26}, {20,27},
{ 0, 3}, { 2, 5}, { 7,10}, { 9,12}, {14,17}, {16,19}, {21,24}, {23,26}, {13,27},
{ 1, 3}, { 2, 4}, { 8,10}, { 9,11}, { 0, 7}, { 5,12}, {15,17}, {16,18}, {22,24}, {23,25}, {14,21}, {19,26},
{ 2, 3}, { 9,10}, { 1, 8}, { 4,11}, { 6,12}, {16,17}, {23,24}, {15,22}, {18,25}, {20,26}, { 0,14},
{ 2, 9}, { 1, 7}, { 3,10}, { 6,11}, {16,23}, {15,21}, {17,24}, {20,25}, {12,26},
{ 2, 8}, { 4,10}, {16,22}, {18,24}, { 1,15}, {11,25}, {13,26},
{ 2, 7}, { 5,10}, { 4, 8}, {16,21}, {19,24}, {18,22}, { 1,14}, {13,25},
{ 6,10}, { 3, 7}, { 5, 9}, {20,24}, {17,21}, {19,23}, { 2,16},
{ 4, 7}, { 6, 9}, {18,21}, {20,23}, { 2,15}, { 3,17}, {10,24},
{ 5, 7}, { 6, 8}, {19,21}, {20,22}, { 2,14}, { 4,18}, { 9,23}, {11,24},
{ 6, 7}, {20,21}, { 4,17}, { 5,19}, { 3,14}, { 8,22}, {12,24},
{ 6,20}, { 5,17}, { 4,15}, { 7,21}, { 9,22}, {13,24}, {12,23},
{ 6,19}, { 4,14}, { 5,16}, { 8,21}, {11,22}, {13,23},
{ 6,18}, { 5,14}, { 9,21}, {13,22},
{ 6,17}, {10,21},
{ 6,16}, {11,21}, {10,17},
{ 6,15}, {12,21}, { 9,16}, {11,18},
{ 6,14}, {13,21}, { 8,15}, {11,17}, {12,19},
{ 7,14}, { 9,15}, {13,20}, {12,17},
{ 8,14}, {13,19}, {11,15}, {12,16},
{ 9,14}, {13,18},
{13,17}, {10,14},
{11,14}, {13,16},
{12,14}, {13,15},
{13,14},
};
static const unsigned int network29[][2] = {
{ 1, 2}, { 3, 4}, { 5, 6}, { 8, 9}, {10,11}, {12,13}, {15,16}, {17,18}, {19,20}, {21,22}, {23,24}, {25,26}, {27,28},
{ 0, 2}, { 3, 5}, { 4, 6}, { 7, 9}, {10,12}, {11,13}, {14,16}, {17,19}, {18,20}, {21,23}, {22,24}, {25,27}, {26,28},
{ 0, 1}, { 4, 5}, { 2, 6}, { 7, 8}, {11,12}, { 9,13}, {14,15}, {18,19}, {16,20}, {22,23}, {26,27}, {21,25}, {24,28},
{ 0, 4}, { 1, 5}, { 7,11}, { 8,12}, { 6,13}, {14,18}, {15,19}, {22,26}, {23,27}, {20,28},
{ 0, 3}, { 2, 5}, { 7,10}, { 9,12}, {14,17}, {16,19}, {22,25}, {24,27}, {13,28},
{ 1, 3}, { 2, 4}, { 8,10}, { 9,11}, { 0, 7}, { 5,12}, {15,17}, {16,18}, {23,25}, {24,26}, {14,22}, {19,27},
{ 2, 3}, { 9,10}, { 1, 8}, { 4,11}, { 6,12}, {16,17}, {24,25}, {14,21}, {15,23}, {18,26}, {20,27},
{ 2, 9}, { 1, 7}, { 3,10}, { 6,11}, {16,24}, {15,21}, {17,25}, {20,26}, {12,27},
{ 2, 8}, { 4,10}, {16,23}, {18,25}, { 0,15}, {11,26}, {13,27},
{ 2, 7}, { 5,10}, { 4, 8}, {16,22}, {19,25}, { 0,14}, {13,26},
{ 6,10}, { 3, 7}, { 5, 9}, {16,21}, {20,25}, {18,22}, {19,23},
{ 4, 7}, { 6, 9}, {17,21}, {20,24}, { 1,16}, {10,25},
{ 5, 7}, { 6, 8}, {18,21}, {20,23}, { 2,17}, { 1,14}, { 9,24}, {11,25},
{ 6, 7}, {19,21}, {20,22}, { 2,16}, { 3,18}, { 8,23}, {12,25},
{20,21}, { 2,15}, { 4,19}, { 7,22}, { 9,23}, {13,25}, {12,24},
{ 2,14}, { 4,18}, { 5,20}, { 6,21}, { 8,22}, {11,23}, {13,24},
{ 6,20}, { 5,18}, { 3,14}, { 4,15}, { 9,22}, {13,23},
{ 6,19}, { 4,14}, { 5,16}, {10,22},
{ 6,18}, { 5,14}, {11,22},
{ 6,17}, {12,22}, {10,18}, {11,19},
{ 6,16}, {13,22}, { 9,17}, {11,18}, {12,20},
{ 6,15}, { 8,16}, {13,21}, {12,18},
{ 6,14}, { 7,15}, { 9,16}, {13,20},
{ 7,14}, { 9,15}, {13,19}, {12,16},
{ 8,14}, {13,18}, {11,15},
{ 9,14}, {13,17},
{10,14}, {13,16},
{11,14}, {13,15},
{12,14},
{13,14},
};
static const unsigned int network30[][2] = {
{ 1, 2}, { 3, 4}, { 5, 6}, { 7, 8}, { 9,10}, {11,12}, {13,14}, {16,17}, {18,19}, {20,21}, {22,23}, {24,25}, {26,27}, {28,29},
{ 0, 2}, { 3, 5}, { 4, 6}, { 7, 9}, { 8,10}, {11,13}, {12,14}, {15,17}, {18,20}, {19,21}, {22,24}, {23,25}, {26,28}, {27,29},
{ 0, 1}, { 4, 5}, { 2, 6}, { 8, 9}, {12,13}, { 7,11}, {10,14}, {15,16}, {19,20}, {17,21}, {23,24}, {27,28}, {22,26}, {25,29},
{ 0, 4}, { 1, 5}, { 8,12}, { 9,13}, { 6,14}, {15,19}, {16,20}, {23,27}, {24,28}, {21,29},
{ 0, 3}, { 2, 5}, { 8,11}, {10,13}, {15,18}, {17,20}, {23,26}, {25,28}, {14,29},
{ 1, 3}, { 2, 4}, { 9,11}, {10,12}, { 0, 8}, { 5,13}, {16,18}, {17,19}, {24,26}, {25,27}, {15,23}, {20,28},
{ 2, 3}, {10,11}, { 0, 7}, { 1, 9}, { 4,12}, { 6,13}, {17,18}, {25,26}, {15,22}, {16,24}, {19,27}, {21,28},
{ 2,10}, { 1, 7}, { 3,11}, { 6,12}, {17,25}, {16,22}, {18,26}, {21,27}, { 0,15}, {13,28},
{ 2, 9}, { 4,11}, {17,24}, {19,26}, { 1,16}, {12,27}, {14,28},
{ 2, 8}, { 5,11}, {17,23}, {20,26}, { 1,15}, {14,27},
{ 2, 7}, { 6,11}, { 4, 8}, { 5, 9}, {17,22}, {21,26}, {19,23}, {20,24},
{ 3, 7}, { 6,10}, {18,22}, {21,25}, { 2,17}, {11,26},
{ 4, 7}, { 6, 9}, {19,22}, {21,24}, { 2,16}, { 3,18}, {10,25}, {12,26},
{ 5, 7}, { 6, 8}, {20,22}, {21,23}, { 2,15}, { 4,19}, { 9,24}, {13,26},
{ 6, 7}, {21,22}, { 4,18}, { 5,20}, { 3,15}, { 8,23}, {10,24}, {14,26},
{ 6,21}, { 5,18}, { 4,16}, { 7,22}, {10,23}, {13,24}, {14,25},
{ 6,20}, { 4,15}, { 5,17}, { 8,22}, {12,23}, {14,24},
{ 6,19}, { 5,15}, { 9,22}, {14,23},
{ 6,18}, {10,22},
{ 6,17}, {11,22}, {10,18},
{ 6,16}, {12,22}, { 9,17}, {11,19},
{ 6,15}, {13,22}, { 8,16}, {10,17}, {12,20},
{14,22}, { 7,15}, {10,16}, {12,19}, {13,21},
{ 8,15}, {14,21}, {13,19}, {12,16},
{ 9,15}, {14,20}, {13,17},
{10,15}, {14,19},
{11,15}, {14,18},
{12,15}, {14,17},
{13,15}, {14,16},
{14,15},
};
static const unsigned int network31[][2] = {
{ 1, 2}, { 3, 4}, { 5, 6}, { 7, 8}, { 9,10}, {11,12}, {13,14}, {15,16}, {17,18}, {19,20}, {21,22}, {23,24}, {25,26}, {27,28}, {29,30},
{ 0, 2}, { 3, 5}, { 4, 6}, { 7, 9}, { 8,10}, {11,13}, {12,14}, {15,17}, {16,18}, {19,21}, {20,22}, {23,25}, {24,26}, {27,29}, {28,30},
{ 0, 1}, { 4, 5}, { 2, 6}, { 8, 9}, {12,13}, { 7,11}, {10,14}, {16,17}, {20,21}, {15,19}, {18,22}, {24,25}, {28,29}, {23,27}, {26,30},
{ 0, 4}, { 1, 5}, { 8,12}, { 9,13}, { 6,14}, {16,20}, {17,21}, {24,28}, {25,29}, {15,23}, {22,30},
{ 0, 3}, { 2, 5}, { 8,11}, {10,13}, {16,19}, {18,21}, {24,27}, {26,29}, {14,30},
{ 1, 3}, { 2, 4}, { 9,11}, {10,12}, { 0, 8}, { 5,13}, {17,19}, {18,20}, {25,27}, {26,28}, {16,24}, {21,29},
{ 2, 3}, {10,11}, { 0, 7}, { 1, 9}, { 4,12}, { 6,13}, {18,19}, {26,27}, {16,23}, {17,25}, {20,28}, {22,29},
{ 2,10}, { 1, 7}, { 3,11}, { 6,12}, {18,26}, {17,23}, {19,27}, {22,28}, { 0,16}, {13,29},
{ 2, 9}, { 4,11}, {18,25}, {20,27}, { 0,15}, { 1,17}, {12,28}, {14,29},
{ 2, 8}, { 5,11}, {18,24}, {21,27}, { 1,15}, {14,28},
{ 2, 7}, { 6,11}, { 4, 8}, { 5, 9}, {18,23}, {22,27}, {20,24}, {21,25},
{ 3, 7}, { 6,10}, {19,23}, {22,26}, { 2,18}, {11,27},
{ 4, 7}, { 6, 9}, {20,23}, {22,25}, { 2,17}, { 3,19}, {10,26}, {12,27},
{ 5, 7}, { 6, 8}, {21,23}, {22,24}, { 2,16}, { 4,20}, { 9,25}, {13,27},
{ 6, 7}, {22,23}, { 2,15}, { 4,19}, { 5,21}, { 8,24}, {10,25}, {14,27},
{ 6,22}, { 5,19}, { 3,15}, { 4,16}, { 7,23}, {10,24}, {13,25}, {14,26},
{ 6,21}, { 4,15}, { 5,17}, { 8,23}, {12,24}, {14,25},
{ 6,20}, { 5,15}, { 9,23}, {14,24},
{ 6,19}, {10,23},
{ 6,18}, {11,23},
{ 6,17}, {12,23}, {10,18}, {11,19},
{ 6,16}, {13,23}, { 9,17}, {12,20},
{ 6,15}, {14,23}, { 8,16}, {10,17}, {12,19}, {13,21},
{ 7,15}, {10,16}, {14,22}, {13,19},
{ 8,15}, {14,21}, {12,16}, {13,17},
{ 9,15}, {14,20},
{10,15}, {14,19},
{11,15}, {14,18},
{12,15}, {14,17},
{13,15}, {14,16},
{14,15},
};
static const unsigned int network32[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11}, {12,13}, {14,15}, {16,17}, {18,19}, {20,21}, {22,23}, {24,25}, {26,27}, {28,29}, {30,31},
{ 0, 2}, { 1, 3}, { 4, 6}, { 5, 7}, { 8,10}, { 9,11}, {12,14}, {13,15}, {16,18}, {17,19}, {20,22}, {21,23}, {24,26}, {25,27}, {28,30}, {29,31},
{ 1, 2}, { 5, 6}, { 0, 4}, { 3, 7}, { 9,10}, {13,14}, { 8,12}, {11,15}, {17,18}, {21,22}, {16,20}, {19,23}, {25,26}, {29,30}, {24,28}, {27,31},
{ 1, 5}, { 2, 6}, { 9,13}, {10,14}, { 0, 8}, { 7,15}, {17,21}, {18,22}, {25,29}, {26,30}, {16,24}, {23,31},
{ 1, 4}, { 3, 6}, { 9,12}, {11,14}, {17,20}, {19,22}, {25,28}, {27,30}, { 0,16}, {15,31},
{ 2, 4}, { 3, 5}, {10,12}, {11,13}, { 1, 9}, { 6,14}, {18,20}, {19,21}, {26,28}, {27,29}, {17,25}, {22,30},
{ 3, 4}, {11,12}, { 1, 8}, { 2,10}, { 5,13}, { 7,14}, {19,20}, {27,28}, {17,24}, {18,26}, {21,29}, {23,30},
{ 3,11}, { 2, 8}, { 4,12}, { 7,13}, {19,27}, {18,24}, {20,28}, {23,29}, { 1,17}, {14,30},
{ 3,10}, { 5,12}, {19,26}, {21,28}, { 1,16}, { 2,18}, {13,29}, {15,30},
{ 3, 9}, { 6,12}, {19,25}, {22,28}, { 2,16}, {15,29},
{ 3, 8}, { 7,12}, { 5, 9}, { 6,10}, {19,24}, {23,28}, {21,25}, {22,26},
{ 4, 8}, { 7,11}, {20,24}, {23,27}, { 3,19}, {12,28},
{ 5, 8}, { 7,10}, {21,24}, {23,26}, { 3,18}, { 4,20}, {11,27}, {13,28},
{ 6, 8}, { 7, 9}, {22,24}, {23,25}, { 3,17}, { 5,21}, {10,26}, {14,28},
{ 7, 8}, {23,24}, { 3,16}, { 5,20}, { 6,22}, { 9,25}, {11,26}, {15,28},
{ 7,23}, { 6,20}, { 4,16}, { 5,17}, { 8,24}, {11,25}, {14,26}, {15,27},
{ 7,22}, { 5,16}, { 6,18}, { 9,24}, {13,25}, {15,26},
{ 7,21}, { 6,16}, {10,24}, {15,25},
{ 7,20}, {11,24},
{ 7,19}, {12,24},
{ 7,18}, {13,24}, {11,19}, {12,20},
{ 7,17}, {14,24}, {10,18}, {13,21},
{ 7,16}, {15,24}, { 9,17}, {11,18}, {13,20}, {14,22},
{ 8,16}, {11,17}, {15,23}, {14,20},
{ 9,16}, {15,22}, {13,17}, {14,18},
{10,16}, {15,21},
{11,16}, {15,20},
{12,16}, {15,19},
{13,16}, {15,18},
{14,16}, {15,17},
{15,16},
};

typedef struct {
const unsigned int comparators;
const unsigned int (*pNetwork)[2];
} Network;

#define elemof(ary) (sizeof(ary)/sizeof(ary[0]))
#define NETWORK(n) {elemof(network##n), network##n}

static const Network networks[] = {
{0, NULL},
{0, NULL},
NETWORK(02),
NETWORK(03),
NETWORK(04),
NETWORK(05),
NETWORK(06),
NETWORK(07),
NETWORK(08),
NETWORK(09),
NETWORK(10),
NETWORK(11),
NETWORK(12),
NETWORK(13),
NETWORK(14),
NETWORK(15),
NETWORK(16),
NETWORK(17),
NETWORK(18),
NETWORK(19),
NETWORK(20),
NETWORK(21),
NETWORK(22),
NETWORK(23),
NETWORK(24),
NETWORK(25),
NETWORK(26),
NETWORK(27),
NETWORK(28),
NETWORK(29),
NETWORK(30),
NETWORK(31),
NETWORK(32),
};
#undef NETWORK

static const size_t cutoff = elemof(networks);

template
inline void networkSort(Elem *p, size_t n) {
const unsigned int (* pNetwork)[2], (* pEnd)[2];
Elem *p0, *p1;
assert(n < elemof(networks)); pNetwork = networks[n].pNetwork; pEnd = pNetwork + networks[n].comparators; for(; pNetwork < pEnd; pNetwork++) { p0 = p + (*pNetwork)[0]; p1 = p + (*pNetwork)[1]; if(*p1 < *p0) swap(p0, p1); } } [/cc]

January 18th, 2011 | 荒唐 | Categories: 数学, 算法 | Comments: No Comments

图灵机vs数学家——图灵机计算能力的分析

（这是我2009年5月在繁星客栈上发表的，现稍加修改放在这里）

这里我尝试回答三个问题
0.是否存在数学家可以做出判定的问题，不存在判定该问题的图灵机？
1.是否存在这样的通用判定图灵机，输入任何数学家可以判定的问题，该图灵机都能在有限步骤之内输出其判定结果，而不输出任何错误的判定结果？
2.是否存在这样的自动判定图灵机，自动尝试判定所有可能的判定问题，而对于其中任何一个数学家可以判定的问题，该图灵机都可以在有限步骤之内输出其判定结果，而不输出任何错误的判定结果？

现在我们对数学家做一个假定：只有能够完全形式化的有限判定过程，才会被数学家承认。
这个假定是合理的，虽然天才的数学家可以用直觉、灵感、做梦、神启等等各种惊人的手段获得一个问题判定结果，但只有能够被彻底形式化的有限判定过程才会被认为是可靠的判定过程。换言之，任何一个能够被数学家认可的判定过程，绝对不能包含任何直觉成分。

上述假定蕴含这样一个结果：
能被数学家承认的任何判定，其步骤数目必然有限。
能被数学家判定的任何问题，其符号刻画必然有限。

有限符号可刻画的问题的全集显然是递归可枚举集，因为它是所有有限长字符串集合的子集，因此可以用自然数i进行编号，记为Pi。
同理，刻画任何有效判定过程的符号串长度必然有限，因此显然是递归可枚举集，也可以用自然数j进行编号，记为Dj。
任何形式系统的推理规则，至多属于乔姆斯基无限制文法的子集，因此推理规则所生成的语言必然是递归可枚举语言的子集，而递归可枚举语言是图灵机可接受（但未必可判定）语言。所有形式系统的推理规则，都可以用自然数k进行编号，记为Lk。

判定【Dj是否为Lk的问题Pi的有效判定过程】，可以用一个通用验证图灵机V(Lk,Pi,Dj)进行判定，而且这是个可判定过程。因为Lk中任何一个判定过程中的任何一个步骤否有效，可以直接套用Lk的推理规则进行判定，而由于整个判定过程的步骤必然有限，因此整个判定过程Dj的有效性必然是可以被图灵机V判定的。

现在我们来构造一个图灵机H(Lk,Pi)，对于给定的形式系统Lk以及Lk的问题Pi，如果Lk中存在对Pi的有效判定过程Dj，那么图灵机H就输出Pi在Lk内的判定结果。但如果Lk中不存在对Pi的有效判定，H永不停机。

为了构造H，我们先考虑一个不可行的构造，然后将其改造为可行的构造：
构造无穷多图灵机Hj(Lk,Pi)，其定义为V(Lk,Pi,Dj)。显然，如果存在某个j，Dj是Pi在Lk下的有效判定，那么Hj必然在有限步骤内停机。
如果将所有的Hj同时启动，那么只要问题Pi在Lk下可判定，那么至少有一个Hj会在有限时间内输出判定，除非问题Pj在Lk下不可判定。

但是上述机构造需要同时运行无数个图灵机，是不可接受的。不过很容易将上述改造为可接受的构造：
构造H(Lk,Pi)，H包含一个循环，在第j次循环中，H先枚举出图灵机Hj的仿真程序，然后将已经枚举出的图灵机H0-Hj的仿真程序分别单步执行一步。显然，H的任何一次循环都必然在有限步骤内结束，只不过越往后循环周期越长。这样，只要Pi在Lk内可判定，那么必然存在某个Hj在运行m个步骤后停机给出判定结果，那么H(Lk,Pi)就必然在第j+m个循环之内停机。反之，如果Pi在Lk内不可判定，那么H永远也不停机。

于是，H就是符合前述要求的图灵机。

现在，我们要利用H(Lk,Pi,Dk)来构造一个永不停机的图灵机X，X不接受任何输入，但X对于任何一个形式系统Lk中任何一个可判定问题Pi，都可以在有限时间内输出其判定结果（连同Lk和Pi的编号一起输出），而对于任何一个不可判定的问题，X都永远不给出对该问题的任何输出。

类似于构造H的过程，我们先考虑一个不可行的构造，然后改造为可行的构造：
二元组(Lk,Pi)显然是一个递归可枚举集，因此可以用自然数n进行编号：n=f(Lk,Pi)，(Lk,Pi)=g(n)，f和g互为反函数。
构造无穷多图灵机Xn，其定义为：如果H(g(n))停机输出判定结果d，Xn就输出(n,d)。显然，只要Pi在Lk中可判定，Xn就必然在有限步骤内停机并输出(n,d)，反之Xn永不停机。
如果将所有的Xn同时启动，那么任何Lk中的任何可判定问题Pi，都必然在有限步骤内被某个Xn输出，输出内容为(n,d)，其中n=f(Lk,Pi)。

上述构造当然也是不可接受的，我们仿照改造H的方法改造X
构造图灵机X，X包含一个循环，在第n次循环中，X先枚举出图灵机Xn的仿真程序，然后将已经枚举出的图灵机X0-Xn的仿真程序分别单步执行一步。显然，X的任何一次循环都必然在有限步骤内结束，只不过越往后循环周期越长。这样，对于任何Lk中的任何Pi，只要Pi在Lk中是可判定的且判定结果为d，那么Xn（n=f(Lk,Pi)）必然在某个有限步骤s处停机并输(n,d)，而Xn的第s步必然在X的第n+s个循环中被执行到，X必然在n+s个循环之内，输出(n,d)。对于任何形式系统中的任何不可判定的问题，X永远都不会输出判定结果。

于是，X就是符合前述要求的图灵机。

现在澄清几件事情：
1.H和X都不会对任何形式系统中的任何不可判定问题给出判定。
2.对于任何Lk中的任何【Pi】，无论【Pi】在Lk中是否可判定，都存在整数i’，使得【Pi’】==【Pi在Lk中可判定】，因此【Pi在Lk中可判定】这个问题迟早会被X枚举出来并尝试对之进行判定。只要【Pi在Lk中可判定】在某个形式系统Lk’中可判定，那么【Pi在Lk中可判定】的判定结果必然会在有限步骤内被X输出。
3.X在枚举Xn的过程中，许多Xn是根本不会停机的，而每次循环中X都必须单步执行所有尚未停机的Xn，因此X的效率会越来越低。但正如我们前面所讨论的，只要一个问题可以判定，X必然会在有限步骤内输出这个问题的判定，X的能力不会随着效率越来越低而变弱。如果实在觉得这种垃圾越来越多的系统很不舒服，那么还存在这样一个优化：每当某个Xn停机输出了某个问题A的判定结果，就检查A的内容是不是在断言另一个问题B不可判定，如果A有效断言出B不可判定，那么就将正在尝试判定B的图灵机从循环中删除。甚至还可以对B做个标记，在枚举新问题的时候，凡是将问题B作为子问题的问题，都将被直接跳过。不过这些优化其实没什么意义，我们的目的仅仅是讨论图灵机的计算能力，并不关心性能。

——————————————————————————————
现在说一点题外话，数学上明明允许图灵机不可判定的问题存在，也允许超越图灵机的计算模型存在，而我们仅仅对数学家做了一个简单的限制，数学家的计算能力就被限制成不超越图灵机了呢？

这个问题很简单。我们所说的形式系统当然都是有限刻画的。数学家可以谈论某些必须由无限符号才能刻画的数学系统的存在性，甚至谈论这些系统的某些能力和限制，但完全无法使用这些系统进行推理。我们之所以可以谈论这些系统的某些能力和限制，是因为精确分析这些东西仅仅需要有限符号。于是，图灵机也一样可以给出关于这些系统的某些有限符号就可以刻画的属性的判定结果。

事实上，即便是我们熟悉的实数集，其中属性能够被有限符号所精确刻画的实数（也包括π、e、γ等）也只是实数集的一个可数子集。

除非数学家可以分辨出连续统那么多不同的符号甚至更多，以至于整个实数轴的每一个实数对于数学家来说一目了然，那么数学家也就具备了Hyper Computing的能力，我在文章开头对数学家所做的假设也就不再成立了。但这种情况下，数学家所能够提出的机械计算模型肯定要比图灵机更强。这种数学家的本事简直赶上上帝了，我们有能力回答的一切数学问题，对于这种超级数学家来说都可以一眼看出答案。

January 17th, 2011 | 荒唐 | Categories: 哲学, 数学, 算法 | Comments: 2 Comments

从计算观点开始……（草稿）

孤立物理体系

所谓孤立物理体系，是指这个体系完全不受其他体系影响，体系的可能状态由体系自身的物理规律所决定。假定为体系选择的一组状态参数的所有取值构成的集和为 $S$ ，那么物理规律就限定了这个集和中那些状态是物理规律所允许的，相当于是对集和 $S$ 的一个约束。可以记为：
$K[s], s\in S$
其中， $K$ 是一个判断， $K[s]$ 为真当且仅当状态 $s\in S$ 是物理规律所允许的。
将所有这样的状态构成的集合记为 $K[S]$ ，显然有 $K[S]\subseteq S$ 。
如果我们的状态参数选取得非常好，参数空间中每一个参数都对应一个符合物理规律的状态，我们就全知了。可惜我们做不到，我们所选择的状态参数所构成的参数空间总是远大于物理规律所允许的状态集。退而求其次，我们希望找到一种等价关系，这种等价关系将状态空间划分为若干个等价类，所有物理规律允许可以共存的现象事件都仅仅属于其中一个等价类，而这个等价类也仅仅包含物理规律允许的现象事件。这样，我们只要找到了这个等价类中的一个代表状态，就可以确定整个等价类。这就是通过初值条件或者边界条件来求解物理体系的方法。

一个简单的例子：一个沿直线匀速运动的粒子，其状态由 $(x,t)$ 标记，运动方程为 $x=v t+x_0$ ，那么仅当 $(x,t)$ 满足这个运动方程时，我们才认为由 $(x,t)$ 所标记的状态才是物理规律所允许的状态。这个例子中所有物理规律所允许的状态的集和刚好构成了粒子的世界线。再举个一维经典标量场的例子：场 $A$ 的状态由函数 $A(x,t)$ 决定。仅当 $(A,x,t)$ 满足场方程 $\frac{\partial^2 A}{{\partial t}^2}-\frac{\partial^2 A}{{\partial x}^2}=0$ 和某个边界条件（例如初始条件 $A(x,0)=A_0(x)$ ）时，我们才认为 $A(x,t)$ 是物理规律所允许的状态。

但上述模型对于物理学家来说只是运动学（Kinematic）模型，只有当你了解了宇宙状态的所有细节才能给出这个运动学方程，而这些细节恰恰是我们希望能够通过方程预言的。换言之这种抽象的运动学模型没什么用。物理学家希望的是：当我了解了宇宙局部的某些信息之后，我可以通过这些信息推算出另一些局部甚至全局的信息。这就要求我们建立所谓的动力学（Dynamical）模型。如果我们知道了宇宙的全部运动学信息，那么动力学模型总是可以导出的，但我们了解到的只是一些局部的信息。

以一维匀速直线运动为例，当我们知道了某个 $(x_0,t_0)$ 是合法物理状态，那么从动力学方程 $\frac{dx}{dt}=v$ 就可以推算出其他的合法物理状态，这个方程告诉我们，如果 $(x_0,t_0)$ 是合法物理状态，那么 $(x+dx,t+dt)$ 要满足什么条件才是合法的物理状态。也就是说，该动力学方程给出了 $(x_0,t_0)$ 和 $(x+dx,t+dt)$ 必须满足的关系，积分后就可以得出 $(x_0,t_0)$ 和任意 $(x_1,t_1)$ 的关系。物理学的动力学视角写成数学方程就是：
$D[S_0,S]=K[S],~where~S_0\subset K[S]$
限定了 $S_0$ 和K[S]必须满足的关系。显然，最平凡的情况是 $S_0=K[S]$ ，但物理学家希望从一组尽可能小的 $S_0$ 出发，通过 $D$ 能够得出整个 $K[S]$ 。比方说匀速直线运动的例子中，从任何一个单独的 $(x_0,t_0)$ 就可以得到所有合法的物理状态。而在上述的一维经典场论中，单独的一个 $(A,x,t)$ 是得不出所有合法物理状态的，必须了解一组状态，比方说了解 $t$ 为某个定值的时候所有 $x$ 对应的 $A$ （初值问题），或者了解曲线 $f(x,t)=0$ 上所有的 $A$ （边值问题），或者了解曲线 $f(x,t)=0$ 上所有的 $\partial A/\partial t, \partial A/\partial x$ （边值问题）。

在经典绝对时空观之中，时间是一个非常特殊的状态参数，所有其他的状态参数都可以写成时间的函数，对于实数、复数、向量、张量等形式的物理量，都可以表达为时间的函数，对于许多物理问题而言，我们都可以根据初值来决定今后的演化：
$D[K[S]|_{t=t_0}, S]=K[S]$
这样一来，这就是所谓经典的机械决定论的视角。进一步，我们可以把这种方程写成关于时间的演化方程：
$K[S]|_{t^+}=F[K[S]|_t]$
如果模型中的时间是连续的，那么可以直接表达为微分方程，令 $s(t)=K[S]|_t$ ：
$\partial s/\partial t=f(s,t)$
在相对论之中，时间不再具有特殊地位，不同参考系也没有一个标准时间，但大家仍然希望能够在时间上做出预言，一个办法是给出物理量在某个完整的类空超曲面上的值，以至于所有的类时世界线都会与这个类空超曲面相交，就可以决定整个时空流形的物理量了。

另一方面，最初用来标记系统状态的状态参量可能具有若干对称性……（待续）

虽然真正的孤立体系要求完全不受外界影响，以至于这样的体系不能从外部通过相互作用来观测，但最初人们认为我们总是可以设法在技术上降低观测对体系的影响，使被观测的体系几乎跟孤立体系没有区别。但近代物理学让人们改变了这种想法，当我们对被观测体系的了解越来越精细，就不得不越来越多地与之相互作用。这种情况下我们需要的是一个相互作用的理论模型，而不是一个孤立体系的理论模型。……（待续）

量子力学实验中往往把宇宙划分为3个部分：被测系统S，观察者和仪器O，环境E。通常要求S只跟O相互作用，但不允许受到E干扰。量子力学的原理体系中扣掉测量原理，描述的就是一个孤立体系的演化。本来应该能够通过孤立体系的演化方程得出一个相互作用的方程，然后计算出观察者观察被测体系将会得到什么结果，但最初大家不知道怎样算，没人会求解整个宇宙的Schr?dinger方程。于是物理学家从实验中得到了一条经验规律：测量原理。遗憾的是测量原理被上升到了量子力学基本原理的地位，引发了Einstein和Bohr旷日持久的争论。到了近代人们逐渐发现测量原理在许多条件下是可以导出的，而且导出的结果比测量原理所给出的细节更多。

————（可逆性、对称性、熵增、可观察量、规范……）

————（引入动机的数学模型，然后是偏好的评价函数，心理，行为，经济，博弈，生态系统，社会……）

开放的物理体系，相互作用

一个孤立体系可以被人为地通过边界划分为两个子系统，这两个子系统通过边界发生相互作用。每一个子系统的所有合法状态自然仍然由整个系统的运动学方程所谓一决定，但我们需要的是得到其中一个子系统的方程，这个方程只跟这个子系统的状态以及另一个子系统在边界上的状态有关……（待续）

孤立机器

所谓孤立机器，就是指这样一种东西：其任意时刻的状态演化方式完全取决于该时刻的状态。
将孤立机器的状态记为 $S$ ，时间记为 $t$ ，后继（Successor）时间记为 $t^+$ （比方说在t连续的情况下， $t^+:=t+dt$ ，离散情况下 $t^+:=t+1$ ），演化规律记为 $U$ ，那么上述定义相应的数学模型为：
$S(t^+) =U[S(t)]$
经典力学中的Hamilton方程就是描述这种孤立机器的方程。在Hamilton力学中，体系的状态用所有粒子的位置和动量来标记，而Hamilton方程则决定了体系状态的演化机制。
$(p,q)(t+dt) = (p,q)(t) + \left(-\frac{\partial H}{\partial q}, +\frac{\partial H}{\partial p}\right)dt$
还有量子力学方程 $\left| \psi (t) \right\rangle = e^{-\mathrm{i}H t}\left| \psi (0) \right\rangle$ ，此时 $U = e^{-\mathrm{i}H t}$

机器

所谓机器，就是指这样一种东西：

跟环境之间有一个分界线
环境在边界上的状态作为机器输入可以改变机器状态
机器在边界上的状态作为机器输出可以改变环境状态
任何时刻其行为和内部状态的变迁完全由该时刻的内部状态和环境输入唯一决定

如果环境也是一台机器，那么可以将环境的状态记为E，那么相应的数学模型为：
$S(t^+) = U[S(t), \partial E(t)]$
$E(t^+) = U[E(t), \partial S(t)]$

孤立机器是机器的特例，如果将环境和机器当作一个孤立整体，那么它又会变为一台孤立机器：
$(S,E)(t^+) = (S(t^+),E(t^+)) = (U[S(t),\partial E(t)],U[E(t),\partial S(t)]) = U[(S,E)(t)]$
如果把系统作为一个整体考虑，那么无论在机器和环境之间如何划界，对结果都是无影响的。

离散的孤立机器

所谓离散的机器，就是上述孤立机器定义中，状态变迁是按步骤跳变的，具有可数内部状态。
对于这样的机器，我们可以用步骤编号 $i$ 代替时间 $t$ ，用 $i+1$ 代替 $t^+$ 。于是其数学模型为：
$S_{i+1} =U[S_i]$

离散的机器

所谓离散的机器，就是上述机器定义中，状态变迁是按步骤跳变的，具有可数内部状态，对环境输入的分类能力也是可数的。
这样一台机器，其时间由步骤标记，记为 $i$ ，于是：
环境从边界给机器的输入记为 $\partial E_i$ ，机器从边界对环境的输出记为 $\partial S_i$ ：
$S_{i+1} = U[S_i, \partial E_i]$
$E_{i+1} = U[E_i, \partial S_i]$

有限状态机器

如果离散的机器的状态数量是有限的，而且只能对环境输入做有限种分类，就叫做有限状态机器。但环境的状态可以是无限的，我们利用有限的时间和资源能够制造出这种机器。图灵机就是一种这样的机器。

图灵机

图灵机是一台有限状态的机器，对于图灵机来说，其环境就是一条无限长的格子纸带（因此环境拥有无限种状态），这个纸带的每一个格子都存贮一个符号，符号的种类是有限的。每一个步骤中，图灵机停泊在纸带上一个特定的位置，可以从这个位置读取符号，然后根据自身状态和读取到的符号唯一地作出一个动作，动作包括向当前位置写入一个符号，然后向左或向右移动一个格子，将自身状态迁移到新的状态。

除此之外，图灵机有一个特殊状态：起始状态，作为每一次执行计算任务的过程的初始状态。还有一组状态作为结束状态，其中一部分被标志为接受，另一部分被标记为拒绝，表示计算任务执行的后果。

可以证明，凡是能够用有限状态机器完成的计算任务，用图灵机都可以完成。还有人进一步证明，通常的神经网络计算模型的计算能力完全等价于图灵机，所谓通常的神经网络计算模型是指这样的神经网络：每一个神经元仅仅有有限种（典型是两种）兴奋状态。

但物理系统经常不是有限状态机器，因此不能简单地说所有的物理系统都等价于图灵机。但是，如果一个由连续参数描述的物理系统，如果对于人类来说可以通过物理量来区分的状态是有限的（比如由于热噪声的存在导致的测量误差），那么这个物理系统对于人类来说计算能力就并不比一个有限状态机器更强。

September 27th, 2010 | 荒唐 | Categories: !Engic, 哲学, 数学, 物理, 算法 | Comments: No Comments

吃苹果游戏和简单回合制游戏的通解

问题：
有20个苹果。
两个人轮流吃，可以吃一个，也可以吃半个。
吃半个的时候，可以吃原来就是半个的，也可以把一个完整的吃掉一半，也就是说可以有很多半个的苹果。
吃一个的时候，只能吃完整的一个。
没有其他选项。
最后吃苹果的人输。

请问，先吃还是后吃的有必胜的策略？这个必胜策略是什么？

答案：
后手有必胜策略。开始的时候先手怎么吃，后手就怎么吃，换言之后手总是设法保持剩下的整苹果和半苹果都是偶数即可。但当剩下的整苹果刚好只有两个的时候，肯定轮到先手吃，而后手此时不能跟先手学。如果先手吃掉一个整苹果，后手就把最后一个整苹果吃掉一半，让半苹果数量变成奇数。如果先手把一个整苹果吃掉一半，那么后手就吃掉最后一个整苹果，保持半苹果是奇数个。由于此时剩下奇数个半苹果，只能轮流吃，后手必胜。

这个问题的答案并不很难找到，通过倒推的方法很容易解决。但对于这类问题，有没有通用的解法呢？
现在就给出一个通用的解法：

通解：

确定游戏的完整状态（或者说局面）参数。比方说上面题目的完整状态参数就是(m,n,p)，m是整苹果的个数，n是半苹果的个数，p是此时由谁行动。
游戏的行动规则确定了状态的迁移规则，或者说从某个状态出发可以到达哪些状态。比方说上面题目从(m,n,p)出发只能到达(m-1,n,~p)——吃一个整苹果、(m,n-1,~p)——吃一个半苹果、(m-1,n+1,~p)——吃半个整苹果，~p表示轮到对方行动。
游戏的初始规则确定了状态空间的出发点。
游戏的获胜规则确定了哪些状态是直接被判定为某一方获胜的。比方说上面问题中(0,0,p)意味着p获胜。在这些状态上，哪个玩家获胜，那么这个状态本身对于这个玩家来说就是有必胜策略的状态（废话，这个状态玩家p都已经获胜了那么p在该状态上当然是有必胜策略的）。
最后一步就是从这些已知的必胜状态出发，递归地确定其他的状态是哪个玩家有必胜策略的状态。如果对于一个玩家来说，根据行动规则某个轮到自己行动的状态存在到达某个自己必胜的状态的行动选择，那么该点对于自己来说也是必胜状态，于是可以递归地将所有的状态都标记上是哪一方必胜，初始状态也会被标记，因此就可以确定初始状态哪一方有必胜策略。

上述解法原则上可以寻找任何完全信息的确定性的回合制的游戏的必胜方和必胜策略。完全信息意思是任何一个回合中，每一个玩家对游戏的局面都有完全的信息，因此不包括桥牌这种不知道对手手中有什么牌的游戏。确定性意思是轮到任何一个玩家行动的时候他可以做出完全确定的行动，因此不包括飞行棋之类需要掷骰子决定如何行动的游戏。回合制意思是参与游戏的若干玩家是按照确定的规则轮流行动的，行为决策是离散的，因此不包括需要连续不断地做行为决策的游戏。类似围棋象棋五子棋跳棋（可以是多方跳棋）的游戏原则上都可以用上述解法寻找必胜方和必胜策略。只不过对于大部分流行的棋类游戏，上述方案会过于庞大以至于无法实际应用。但对于前面这种可以用于做智力题的完全信息确定回合制游戏，用上述通用解法大都可以迅速找到必胜方和必胜策略。

现在以前面的问题为例来说明这个通用解法。由于规则是两个人交替行动，所以(m,n,p)里面的p可以省略，用(m,n)代表状态就可以了，于是状态空间就变成了二维平面上的格点空间。而游戏的行动规则决定了从一个格点出发可以到达哪些格点。注意，由于取消了参数p，所以(0,0)状态无法确定谁胜谁负，但只有一个半苹果的状态(0,1)显然是后手必胜，因为先手只能吃掉这半个苹果而输掉游戏。另外，只有一个整苹果的状态(1,0)显然是先手必胜，但这一点可以通过(0,1)是后手必胜来导出，因此是可有可无的。有了这一个确定的格点，其他所有的格点先手还是后手有必胜策略都可以确定了：对于任何一个格点S，如果从S出发能够到达的所有格点全都是先手有必胜策略的格点，那么S就是后手有必胜策略的格点（因为后手在下一步变为先手）。否则，如果从S出发能够到达的格点之中至少有一个是后手有必胜策略的格点，那么S就是先手有必胜策略的格点（因为先手可以选择进入这个后手必胜的格点，自己同时变成后手）。

上图中，直接确定了(0,1)、(1,0)两个画圈的点的必胜方和必胜策略。图中选了几个典型的点示范了其他点的颜色是如何确定的：凡是从该点出发只能到达绿色点的点都涂成红色，凡是从该点出发至少有一个目标点是红色的点都涂成绿色。从两个画圈的点出发（其实只从(0,1)出发就够了），可以递归确定所有点的颜色。只需要做几步就可以发现规律得到答案。

September 1st, 2010 | 荒唐 | Tags: 博弈, 游戏.
Categories: 数学, 灵感, 算法 | Comments: No Comments

简单回合制游戏

Reinvent wheels, my quick sort implementation, just for fun

Finding all paths from source to destination

Sorting network

图灵机vs数学家——图灵机计算能力的分析

从计算观点开始……（草稿）

吃苹果游戏和简单回合制游戏的通解

欢迎你来到这里。

Recent Comments

Tag Cloud

Categories

Recent Posts

Archives

!Engic

人物

刊物

娱乐

工具

我的

新闻

知识

论坛

资源

链接

Meta