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

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; 

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

Answer 1

Это будет легко с рекурсивным алгоритмом лечения вашего списка четверного по состоянию на , которые имеют 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

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

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

---

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

Однако, мы должны добавить логическое значение в STRUCT номер, чтобы избежать бесконечного поиска, потому что ваши номера могут петли друг на друга, как это:

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 
} 

Answer 3

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

Для обучения 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/