Я применил алгоритм поиска с возвратом к проблеме Фермер, Волк, Коза и Капуста — чтобы увидеть, есть ли какие-либо интересно ветви, помимо (двух) 7-ступенчатых решений.
Проблема WGC: Фермер с волком, козой и гигантской капустой должен пересечь реку на крошечной лодке, которая может нести только ему плюс один из трех грузовых грузов. Проблема в том, что Козел начинает есть капусту, как только Фермер оказывается на Другой сторона. В Волк делает то же самое с козой. Может ли он переправить всех троих на другую сторону согласно этим правилам / ограничениям?
У sakharov.net очень красивое описание (он называется «русский»). Я давно читал, что следы рассказа теряются в средневековье. Капуста (щи) и волк (Питер) — типичные русские вещи. Вот версия Сахарова:
Это старая и известная русская головоломка. Попробуйте переправить Волка, Козу и Капусту через реку на лодке. Вы можете брать с собой на лодку только одного из них в каждую поездку. Если оставить Волка и Козла на одном берегу, Волк съест Козу. Если вы оставите Козу и Капусту на одном берегу, Коза съест Капусту. Хотя они никогда не съедят друг друга, пока вы остаетесь с ними. Убедитесь, что все они благополучно достигли другого берега реки.
Тогда можно реально «поиграть». Погрузка и разгрузка отделены от переезда, это хороший способ немного отвлечь игрока. Вы получаете сообщение, когда делаете «незаконный» ход.
Вы можете переместить человек / животное / объект на лодку, нажав на ее изображение. Щелчок по изображению в лодке перемещает его назад.
Чтобы переместить лодку на другой берег, нажмите кнопки «>».
человек / животное / объект: У меня была такая же проблема. Я выбрал «Животные». Сейчас неправильно превращать «капусту» в «салат». Но салат (для меня) съедобен, как опасен волк. Некоторые используют лису, курицу и фасоль. Некоторые продают свою душу только для того, чтобы расширить проблему и назвать ее каннибалами и миссионерами.
Я подумываю добавить интерактивную версию (называемую вместо backtrack_fsgw() из main()), давая пользователю (который должен играть вслепую) такие сообщения, как:
«Не могу взять салат. Коза и волк останутся вместе».
«Козы здесь нет»
«Ты только что привел волка с той стороны»
«Вы вращаетесь по кругу. Вы были с козой на той стороне 6 переходов назад»
На первый взгляд это кажется дилеммой. Тогда вы это понимаете может быть решенным (вернув козла на шаг 4). Тогда вы понимаете: это может почти не быть нерешенным: каждый выбор обязателен, кроме глупых прямых повторений.
Вы должны внимательно присмотреться, чтобы найти способ продлить процедуру, постоянно меняя 3 пассажира. Вместо того, чтобы возвращаться в конце с пустыми руками за одинокой козой, вы можете забрать волка или салат, что бы вы ни сделали. нет нести в последнюю очередь. (если вы выберете другой, это не начало цикла, а (глупое) прямое повторение)
Вот результат. Фермер (= пустой паром), Салат, Коза и Волк — 0, 1, 2 и 3 соответственно.
ALL CROSSED - Level= 7 2012302
ALL CROSSED - Level=13 2012312312302
ALL CROSSED - Level=19 2012312312312312302
ALL CROSSED - Level=25 2012312312312312312312302
ALL CROSSED - Level=31 2012312312312312312312312312302
MAXLEVEL reached - backtracking to escape cycle: ...12312312
ALL CROSSED - Level= 7 2032102
ALL CROSSED - Level=13 2032132132102
ALL CROSSED - Level=19 2032132132132132102
ALL CROSSED - Level=25 2032132132132132132132102
ALL CROSSED - Level=31 2032132132132132132132132132102
MAXLEVEL reached - backtracking to escape cycle: ...32132132
Конечно, он продолжает находить «решения», если не останавливается на maxlevel. Это своего рода доброкачественный, неразветвленный цикл. Включая глупых повторений, вы получаете огромное количество скучных ответвлений.
Это отфильтрованные выходные строки (оба вида).
Полный вывод отображает «состояние берегов реки». Вот строки 20-70 с первым решением.
...
[ 5 LEVEL] cur:[-1] parent: 2
0: *.**
1: .*..
--> new node:[3] and state:
0: ..*.
1: **.*
[ 6 LEVEL] cur:[-1] parent: 3
0: ..*.
1: **.*
--> new node:[0] and state:
0: *.*.
1: .*.*
[ 7 LEVEL] cur:[-1] parent: 0
0: *.*.
1: .*.*
--> new node:[2] and state:
0: ....
1: ****
ALL CROSSED - Level= 7 2012302
[ 6 LEVEL] cur:[0] parent: 3
0: ..*.
1: **.*
--> new node:[1] and state:
0: ***.
1: ...*
...
Это резюмирует то, что делает программа.
К моему удивлению, у меня получился 3D-массив через typedef. С int **sh Я должен был использовать это как (*sh)[fside]. А также другие предупреждения и ошибки, связанные с указателем, а не массивом. Теперь это:
next_node(Shores_t sh, ...
...
ferry(sh, anim, fside);
if (is_unsafe(sh[fside]))
Вопросов:
Думаю, если вам нужны массивы, это один из многих правильных способов сделать это. Может работать даже с переменным размером стека / стеком времени выполнения.
Был бы struct shores быть более гибким для передачи, для помещения в массив и для доступа?
Что поместить внутрь этой структуры? Я не думаю sh.goat работает, если элемент перечисления Goat целое число 2. Может быть, лучший вариант, если использовать чистую логику.
Или я просто сворачивать а structвокруг существующего typedef?
struct shores { Shores_t sht };
а потом sh->sht[Dest][Farmer] ?
Это даже хуже, чем (*sh)[Dest][Farmer].
Должен ли я делать массив указателей? Как обычно с динамическими 2D-массивами?
Для хранения полного состояния было бы достаточно восьми или даже четырех битов. Но я не хочу, чтобы он был маленьким и быстрым.
Есть какие-нибудь общие идеи для этого конкретного случая?
Есть комментарии по поводу кода ниже?
/* Farmer, Wolf, Goat and Cabbage
River Crossing Problem/Puzzle/Dilemma
Here the cabbage is a salad - "fsgw" instead of FWGC (or FCGW).
The 'none' option (or 'Alone') was renamed 'Farmer' to use it better
(see all_on_side() and ferry()). These four items (symbols) are numerically represented
as 'Animals' (as living beings) via enum.
The first Shores_t (both Sides_t of the river) looks like:
{ {1,1,1,1}, {0,0,0,0} }
This is a bit redundant, but robust/clear (see is_unsafe()).
Alternative: only 4 bools e.g. "1010" as "FcGw"; the other side then is virtual/the inverse.
By avoiding simple node/move repeats (ferry *directly* back what you just ferried),
there is only a 3-cycle pattern (rotating the items after 6 cycles) amd it can easily be broken.
An alternative would be to check for *state* repetitions in the *whole* stack. */
#include <stdio.h>
#include <string.h>
/* For different backtrack patterns (and for testing) the sequence can be changed */
enum {Farmer, Salad, Goat, Wolf, Animals};
//enum {Salad, Wolf, Goat, Farmer, Animals};
enum {Start, Dest, Sides};
typedef int Side_t [Animals]; /* For real 2D array without 'int...[2][4]' everywhere */
typedef Side_t Shores_t [Sides];
int
is_unsafe(Side_t b) { /* b: where the farmer is NOT */
return b[Goat] && ( b[Salad] || b[Wolf] );
}
int
all_on_side(Side_t d) { /* d: 'Dest' side to test for success */
return d[Farmer] && d[Salad] && d[Goat] && d[Wolf];
}
/* Visualize a "shore[2][4]" (Two sides with four slots).
A bit of Conway life, just as jumpy on small scale */
/* The enum determines which of f,s,g and w is 0,1,2 or 3 */
void
show_state(Shores_t sh) {
for (int s = 0; s < Sides; s++) {
printf("%d: ", s);
for (int i = 0; i < Animals; i++)
printf(sh[s][i] ? "*" : ".");
putchar('n');
}
}
/* Show chain of nodes up to level 'end', for solutions. One-based. */
void
show_nodes(int *n, int end) {
for (int i = 1; i <= end; i++)
printf("%d", n[i]);
putchar('n');
}
/* Cross the river alone or with an 'anim' =
Check-out at 'from' and check-in at NOT-'from' */
void
ferry(Shores_t sh, int anim, int from) {
int to = !from;
sh[from][anim] = 0;
sh[to] [anim] = 1;
if (anim != Farmer) { /* (or just repeat with same value) */
sh[from][Farmer] = 0;
sh[to] [Farmer] = 1;
}
}
/* Returns next valid node, above current, and different from lower node (no direct repetition!). */
/* Or -1 if none left. Also updates the state stack by reference 'Shores_t sh'. */
int
next_node(Shores_t sh, Shores_t sh_0, int anim, int anim_0) {
memcpy(sh, sh_0, sizeof(Shores_t)); /* Work on last state in new level on stack */
const int fside = sh[1][Farmer]; /* Where is the farmer at all? (note [1], not [Dest], makes that trick (?) less confusing)*/
while (++anim < Animals) {
if (sh[fside][anim] && anim != anim_0) {
ferry(sh, anim, fside); /* Test crossing... */
if (is_unsafe(sh[fside]))
ferry(sh, anim, !fside); /* ...undone by ferry() in reverse */
else
return anim; /* ...confirmed, done */
}
}
return -1;
}
/* Backtrack FWGC (fsgw) using next_node() */
/* With indep. tests for max. level (cycle breaker) and for end state */
void
backtrack_fsgw(int *nodes, Shores_t *states, int MAX) {
int LVL = 1;
while (LVL > 0) {
/* Display I: current level, old vars */
printf("[%2.d LEVEL] cur:[%d] parent: %dn", LVL, nodes[LVL], nodes[LVL-1]);
show_state(states[LVL-1]);
nodes[LVL] = next_node(states[LVL], states[LVL-1],
nodes[LVL], nodes[LVL-1]);
if (nodes[LVL] == -1)
LVL--;
else {
/* Display II: after successful next_node() */
printf(" --> new node:[%d] and state: n", nodes[LVL]);
show_state(states[LVL]);
putchar('n');
if (all_on_side(states[LVL][Dest])) {
printf("ALL CROSSED - Level=%2.d ", LVL);
show_nodes(nodes, LVL);
nodes[LVL--] = -1;
continue;
}
if (LVL == MAX) {
printf("MAXLEVEL reached - backtracking to escape cycle: ...");
show_nodes(&nodes[LVL-8], 8); /* not too much back, if MAX is very low...todo; but then again it only shows 123... or 321... */
nodes[LVL--] = -1;
continue;
}
LVL++;
}
}
return;
}
/* Stacks for (i.e. Arrays of) the nodes (moves) and the states (Shores_t, int[2][4]) */
int main(void) {
/* Maximum level:
- 32 is enough to give solution pairs at levels 7, 13, 19, 25 and 31. Also enough crossings to give up.
- 8 is enough for the first/best solution pair */
#define MAXLEV 32
int nodes [MAXLEV];
Shores_t states[MAXLEV];
int i;
/* Unvisited nodes have -1 */
for (i = 0; i < MAXLEV; i++)
nodes[i] = -1;
/* Starting position of F,S,G,W on Shore Zero */
for (i = 0; i < Animals; i++) {
states[0][Start][i] = 1;
states[0][Dest] [i] = 0;
}
backtrack_fsgw(nodes, states, MAXLEV-1);
return 0;
}
1 ответ
(* ап)[x][y]
Вот как использовать указатель на массив после его объявления и назначения вручную. Начиная с 3D-массива a…
int a[100][2][4];
a[16][1][2] = 123456;
… Есть два способа получить «ссылку» на a[xx]. С или без typedef int Shores_t[2][4]. Я даже беру a[14] а потом [1+4][2], поскольку первый индекс не обязателен / массив не имеет границ.
int (*p)[][4] = (int (*)[][4]) a[14];
/* Same as: */
Shores_t *p = (Shores_t *) a[14];
Теперь я могу получить доступ ко всем значениям относительно a[14]
printf("%dn", (*p)[5][2]);
И я получаю номер a[16][1][2]. Я пропустил четыре ...[0] и ...[1] записи в a[14] и a[15].
Без приведения с правой стороны вы получите предупреждение компилятора. И в конце концов вы даже не можете использовать п[..., but (*p)[..., to fight against precedence rules.
The «right» way to do it is to use functions — call it with a naked a[16] как аргумент и объявить как массив p правильного типа.
typedefs и параметры функций
Переименовав Sides_t с FSGW_t, и дублируя его вручную, вы тоже можете жить без Shores_t. Вот несколько идей:
Размеры массива [2][4] можно было бы более «официально» назвать:
enum {Farmer, Salad, Goat, Wolf, N_fsgw};
enum {Start, Dest, N_sides};
Массив из 4 целых чисел (т.е. F, S, G и W):
typedef int FSGW_t [N_fsgw];
//typedef FSGW_t Shores_t [N_sides];
В main():
FSGW_t states[MAXLEV][2];
или даже:
int states[MAXLEV][2][4]; // 2 sides, 4 items FSGW
чтобы увидеть все это.
В backtrack_fsgw() декларация является одним из:
//backtrack_fsgw(int *nodes, Shores_t *states, int MAX) {
backtrack_fsgw(int *nodes, int states[][2][4], int MAX) {
backtrack_fsgw(int *nodes, int (*states)[2][4], int MAX) {
backtrack_fsgw(int nodes[], FSGW_t states[][2], int MAX) {
…
В next_node() есть небольшая проблема без sizeof(Shores_t).
int
next_node(FSGW_t sh[], void *sh_0, int anim, int anim_0) {
//memcpy(sh, sh_0, sizeof(FSGW_t)*2);
//memcpy(sh, sh_0, sizeof(FSGW_t[2]));
//memcpy(sh, sh_0, sizeof(int[2][4]));
memcpy(sh, sh_0, (void*)sh - sh_0);
Я предпочитаю последнюю версию: она показывает, что нам нужен только адрес и размер sh_0. sizeof sh не работает, потому что это «всего лишь» массив параметров.
(Но для этого не нужны паренсы (*sh)[...]. Это массив 3/4.
ferry(FSGW_t sh[2], int anim, int from) {
…или же sh[] или же *sh. Цифра «2» предназначена только для предоставления информации и отражает ограниченный диапазон «от» и «до» (0 и 1).
Затем возвращаемся наверх:
int
is_unsafe(FSGW_t b) { /* b: where the farmer is NOT */
return b[Goat] && ( b[Salad] || b[Wolf] )
Я не говорю этого FSGW_t версия single typedef лучше, чем Side_t/Shores_t версия. Я просто хотел показать, как обрабатывать несколько слоев массивов, даже если нет соответствия typedef
Правило массива: «Первое измерение — бесплатно» (остальные — нет). Первый [] справа такой же, как (*...) вокруг идентификатора.