Пошук в графі з критерієм ваги!!!

Приклад графа де вибір найнижчої вартості для першого вузла не дає найкращого результату

Поняття

Пошук з критерієм ваги (вартості) (UCS) можна застосувати, щоб знайти найнижчу вартість через граф, зберігаючи упорядкований список вузлів у порядку зниження ваги. Це дозволяє нам оцінити найменший рівень витрат з самого початку.

Алгоритм UCS використовує накопичену вартість шляху для визначення шляху для оцінки. Черга пріоритетів (відсортована від найменшої вартості до найбільшої) містить вузли для оцінювання. Оскільки діти вузлів оцінюються, ми додаємо їхню вартість до вузла з сукупною сумою поточного шляху. Цей вузол потім додається до черги, а коли всі діти оцінюються, то черга сортується в порядку зростання вартості. Коли першим елементом у черзі на пріоритет є цільовий вузол, то знайдено найкраще рішення.

UCS є оптимальним і може бути повним, але тільки в тому випадку, якщо вартість дуг невід'ємна (сумарна вартість маршруту завжди зростає). Складність часу та простору є такою ж, як BFS, O (b^d) для кожного.

Перебіг пошуку

Оцінка вузлів і стан черги пріоритетів

Ілюстрація вартості шляху в графі

На першому кроці початковий вузол був доданий до черги для пріоритетів, з вартістю нуль. На другому кроці кожний із трьох пов'язаних вузлів оцінюється та додається в чергу пріоритету. Коли жоден дочірній вузол не доступний для оцінки, черга пріоритетів сортується, щоб розмістити їх у порядку зростання вартості.

На третьому етапі оцінюються дочірні вузли С. У цьому випадку ми знаходимо бажану ціль (E), але оскільки накопичена ціна шляху становить вісім, вона закінчується в кінці черги. Для четвертого етапу ми оцінюємо вузол D та знову шукаємо цільовий вузол. Ціна шляху дорівнює семи, що все ще перевершує наш вузол B у черзі. Нарешті, на п’ятому етапі, оцінюється вузол В. Цільовий вузол знайдено знову, при цьому вартість маршруту становить шість. Черга пріоритету тепер містить цільовий вузол у верхній частині, що означає, що на наступній ітерації циклу алгоритм вийде з шляху A-> B-> E (працює назад від цільового вузла до початкового вузла).

Щоб обмежити розмір черги для пріоритетів, можна стерти записи, які є надлишковими. Наприклад, на кроці 4, запис про E (8) можна було б безпечно видалити, оскільки існує інший шлях, який має нижчу вартість (E (7)).

Реалізація

#include <stdio.h> 
#include “graph.h” 
#include “pqueue.h” 
#define A 0 
#define B 1 
#define C 2 
#define D 3 
#define E 4 
int init_graph( graph_t *g_p ) 
{
  addEdge( g_p, A, B, 5 );
  addEdge( g_p, A, C, 1 );
  addEdge( g_p, A, D, 2 );
  addEdge( g_p, B, E, 1 );
  addEdge( g_p, C, E, 7 );
  addEdge( g_p, D, E, 5 );
  return 0; 
}
void ucs( graph_t *g_p, int root, int goal ) 
{
  int node, cost, child_cost;
  int to;  pqueue_t *q_p;
  q_p = createPQueue( 7 );
  enPQueue( q_p, root, 0 );
  while ( !isEmptyPQueue(q_p) ) 
  {
    dePQueue( q_p, &node, &cost );
    if (node == goal) 
    {
      printf(“cost %d\n”, cost);
      return;
    }
    for (to = g_p->nodes-1 ; to > 0 ; to--) 
{
      child_cost = getEdge( g_p, node, to );
      if (child_cost) 
      {
        enPQueue( q_p, to, (child_cost+cost) );
      }
    }
  }
  destroyPQueue( q_p );
  return;
 }
 int main() 
{
  graph_t *g_p;
  g_p = createGraph( 6 );
  init_graph( g_p );
  ucs( g_p, A, E );
  destroyGraph( g_p );
  return 0;
 }

Допоміжний АРІ

Для демонстрації алгоритмів пошуку необхідний допоміжний АРІ, що включає перелічені функції:

/* Graph API */ 
graph_t *createGraph (int nodes ); 
void destroyGraph (graph_t *g_p ); 
void addEdge (graph_t *g_p, int from, int to, int value ); 
int getEdge (graph_t *g_p, int from, int to ); 
/* Stack API */ 
stack_t  *createStack (int depth ); 
void destroyStack (stack_t *s_p ); 
void pushStack (stack_t *s_p, int value ); 
int popStack (stack_t *s_p ); 
int isEmptyStack (stack_t *s_p ); 
/* Queue API */ 
queue_t  *createQueue (int depth ); 
void destroyQueue (queue_t *q_p ); 
void enQueue (queue_t *q_p, int value ); 
int deQueue (queue_t *q_p ); 
int isEmptyQueue (queue_t *q_p ); 
/* Priority Queue API */ 
pqueue_t *createPQueue (int depth );
void destroyPQueue (pqueue_t *q_p ); 
void enPQueue (pqueue_t *q_p, int value, int cost ); 
void dePQueue (pqueue_t *q_p, int *value, int *cost ); 
int isEmptyPQueue (pqueue_t *q_p ); 
int isFullPQueue (pqueue_t *q_p );

Виконав Романів Роман

Developed by Інститут Програмних Систем