Я ищу конкретный алгоритм поиска

Question

В настоящее время я пытаюсь создать небольшой текстовый сканер подземелий на C, где карта должна генерироваться случайным образом. Я пытаюсь сделать это с помощью четырехсвязного списка, где каждый узел (комната) может иметь до четырех подключений к следующим комнатам.

typedef struct Room {
    int x; //each room got its own number to be identified.
    struct Room *north;
    struct Room *east;
    struct Room *south;
    struct Room *west; } room;

Для некоторых комнат также должно быть возможно иметь только одно, два или три соединения, в то время как неиспользуемые указатели на следующие узлы остаются пустыми. По разным причинам мне нужен алгоритм поиска, который перебирает комнаты, чтобы найти конкретный. Я понятия не имею, как реализовать что-то вроде этого. Есть идеи?

Answer 1

Это будет легко с рекурсивным алгоритмом, обработайте ваш список квадратов с graph который имеет left, right, top а также bottom connection.Following - это псевдокод для вашего алгоритма поиска:

typedef enum{
    VISITED,
    NOT_VISITED
}status;
typedef struct vertex{
    int x;
    struct vertex* up;
    struct vertex* down;
    struct vertex* left;
    struct vertex* right;
    status node_status;
}node;
typedef struct{
    node* g_nodes;
    int capacity, length, width,curr_filled;
    int row_index, col_index;
}graph;
g_node* search_graph (graph* gph, int key)
{
    static g_node = get_first_node ( gph ); //you can get any node.
    if ( g_node->x == key){
        return g_node;
    }
    if ( g_node->node_status == VISITED){
        return NULL;
    } 
    g_node->node_status = VISITED;
    if (g_node->left != NULL){
        return search_graph (gph, g_node->left);
    }
    if (g_node->right != NULL){
        return print_graph (gph, g_node->right);
    }
    if (g_node->up != NULL){
        return print_graph (gph, g_node->up);
    }
    if (g_node->down != NULL){
        return print_graph (gph, g_node->down);
    }

}  

Answer 2

Я думаю, что Вы можете использовать метод глубинного поиска для нахождения желаемого значения. Поскольку может быть возможно найти четыре стороны, поэтому этот алгоритм поможет Вам найти.

Для изучения DFS (глубины первого поиска) Вы можете прочитать эти:)

http://en.wikipedia.org/wiki/Depth-first_search

http://www.ics.uci.edu/~eppstein/161/960215.html

http://www.geeksforgeeks.org/applications-of-depth-first-search/

Answer 3

Простым решением было бы создать массив Roomили массив Room *

Затем вы можете искать в массиве с помощью цикла, пока не найдете комнату с искомым значением xили достигните конца массива.

---

Если вы начинаете с начальной комнаты, вы можете попробовать рекурсивный поиск в цепочечном списке.

Тем не менее, мы должны добавить bool в структуру Room, чтобы избежать бесконечного поиска, потому что ваши комнаты могут зацикливаться друг на друге так:

 O--O
 |  |
 O--O
  O : room, - and | : link between rooms

checked значение должно быть инициализировано false перед началом поиска, и этот параметр получает true когда номер проверен один раз.

принцип:

Room* search_room (int x_search, Room* current_room)
{
//if current_room is NULL, return NULL
//if checked is true, return NULL
//checked becomes true
//if current_room->x equals x_search, return current_room

//store the result of search_room(x_search, current_room->north) somewhere
//if it's not null, return what it has returned
//if not, then proceed to the store and check of the 3 others calls :
//search_room(x_search, current_room->east)
//search_room(x_search, current_room->south)
//search_room(x_search, current_room->west)

//if all the 4 calls returned NULL, return NULL
}