Shaharlar orasidagi eng qisqa masofa

Salom. Ushbu maqola ham buyurtma asosida yozildi. Buyurtma quyidagicha: «Shaharlar orasidagi eng qisqa masofa». Buni o'zim ham oldin qilmoqchi bo'lib yurgan edim lekin vaqt bo'lmaganidanmi yoki zarurat bo'lmaganidan umuman qiziqmaganman. Bugun mana qiziqishimga sabab bo'ldi.

Bilamizki ikki shahar orasidagi masofa desa ko'pchilikni oldiga «Graph» tushunchasi keladi. Graph haqida:

http://en.wikipedia.org/wiki/Graph_(mathematics)

Umuman man yozmoqchi bo'lgan algoritm quyidagicha: Bizda shaharlar bor, ikkita shahar orasidagi masofani topish uchun shu ikkita shahar orasidagi masofalarni barchasini hisoblab chiqamiz va shularning ichidan eng kichigini olamiz.

Keling kod yozishga o'tamiz. Birinchi shahar haqidagi ma'lumotni saqlaydigan struktura

struct city {
 char name; //shahar nomi
 char used; //qidirish paytida kerak
 int distance_count; //shu shahardan boshqa nechta shaharga to'g'ri yo'l mavjud
 struct city_distance** distances; //borishi mumkin bo'lgan shaharlar va masofalar ro'yxati
};

Endi ikkinchi struktura city_distance

struct city_distance {
 struct city *to; //qaysi shaharga borishi
 int distance; //orasidagi masofa
};

Bu ikkala struktura shahar va shaharlar orasidagi masofani aniqlaydigan strukturalar edi. Endi shaharlarni yaratamiz.

unsigned char i; //o'zgaruvchi

//jami shaharlarning ro'yxatini saqlaydi
struct city** cities_list = (struct city **)calloc(city_count, sizeof(struct city));
for(i = 0; i < city_count; i++)
{
 //yangi shahar yaratish
 struct city * c = (struct city *)malloc(sizeof(struct city));
 c->used = 0;
 c->name = 'A' + i; //i0 = 'A', i1 = 'B', ...
 
 //boshlang'ich ma'lumotlarni berish
 c->distance_count = 0;
 c->distances = NULL;
 
 //ro'yxatga qo'shish
 cities_list[i] = c;
}

Endi shaharlarning orasidagi masofalarni kiritamiz, buning uchun man quyidagi funksiyani yozdim

void _add_distance(struct city *from, struct city *to, int distance)
{
 int index = from->distance_count, i = 0;
 
 //ro'yxatni bittaga oshirish
 from->distance_count++;
 
 if (from->distance_count == 1) //birinchi marotaba
 {
 //ro'yxatni saqlaydigan strukturlar massivini yaratish
 from->distances = (struct city_distance**)calloc(1, sizeof(struct city_distance));
 }
 else
 {
 //tekshirish, bitta shahar ikki marotaba qo'shilganligini
 for(; i < from->distance_count - 1; i++)
 {
 if (from->distances[i]->to->name == to->name)
 {
 from->distances[i]->distance = distance;
 from->distance_count--;
 return;
 }
 }

 //agar yangi bo'lsa, massivni o'lshamini bittaga oshiramiz
 from->distances = (struct city_distance**)realloc(from->distances, from->distance_count * sizeof(struct city_distance));
 }

 //qo'shilgan shahar ma'lumotlarnini berish
 from->distances[index] = (struct city_distance *) malloc(sizeof(struct city_distance));
 from->distances[index]->to = to;
 from->distances[index]->distance = distance;
}

//bu from => to, to => from, ya'ni ikkita shaharda bir biriga borsa bo'ladi
//degan shart uchun
void add_distance(struct city *from, struct city *to, int distance)
{
 _add_distance(from, to, distance);
 _add_distance(to, from, distance);
}

Agar kodga qaragan bo'lsangiz bir vaqtning o'zida A shahardan B ga va B shaharda A ga bo'lgan masofalar qo'shilyapti. Bu koddan shunday foydalansa bo'ladiki, ya'ni agar A dan B borsa bo'ladi lekin B dan aga borib bo'lmaydi shartini ham bersa bo'ladi. Agar zarur bo'lsa.

Man yozgan kodni testlashim uchun quyidagi graph dan foydalandim:

Endi shu graphni kodda yasash uchun

//A => B = 1000
add_distance(cities_list[0], cities_list[1], 1000);
//A => C = 1000
add_distance(cities_list[0], cities_list[2], 1000);
//A => D = 1500
add_distance(cities_list[0], cities_list[3], 1500);
//B => C = 1400
add_distance(cities_list[1], cities_list[2], 1400);
//B => D = 800
add_distance(cities_list[1], cities_list[3], 800);
//B => E = 1700
add_distance(cities_list[1], cities_list[4], 1700);
//B => F = 2600
add_distance(cities_list[1], cities_list[4], 2600);
//C => D = 700
add_distance(cities_list[2], cities_list[3], 700);
//C => F = 2800
add_distance(cities_list[2], cities_list[5], 2800);
//D => E = 1200
add_distance(cities_list[3], cities_list[4], 1200);
//D => F = 1600
add_distance(cities_list[3], cities_list[5], 1600);
//E => F = 900
add_distance(cities_list[4], cities_list[5], 900);

kodni yozishimiz kerak, hamma sonlar o'zimni birligimda ko'rsatilgan. Hohlasangiz SM, M, KM ko'rinishida olishingiz mumkin.
Biz shu joygacha graphni yasab chiqdik, endi eng asosiysi ikkita shahar orasidagi eng qisqa masofani topish.

char search_steps[10] = ""; //qidirishdagi qadamlarni saqlash
char search_min_steps[10] = ""; //eng qisqa masofa qadamlarini saqlash
int search_min_distance = -1; //eng qisqa masofa

void search(struct city *from, struct city *to, int search_step, int found_distance)
{
 int i = 0;
 struct city_distance * cd;
 search_steps[search_step] = from->name;
 search_steps[search_step + 1] = '\0';

 /**
 * COMMNET 1
 if (search_min_distance != -1 && found_distance > search_min_distance)
 {
 return;
 }
 */

 if (from->name == to->name)
 {
 if (search_min_distance == -1 || found_distance < search_min_distance)
 {
 search_min_distance = found_distance;
 strncpy(&search_min_steps[0], &search_steps[0], 10);
 }

 printf("%s = %d\n", search_steps, found_distance);
 return;
 }

 from->used = 1;

 for(; i < from->distance_count; i++)
 {
 cd = from->distances[i];
 if (cd->to->used == 1)
 continue;
 
 search(cd->to, to, search_step + 1, found_distance + cd->distance);
 }

 from->used = 0;
}

Bu kod qanday ishlaydi. Pastdagi animatsiyani ko'ring, kodning har bir qidirish qadami ko'rsatilgan. Ya'ni A dan F gacha bo'lgan masofani topishda kod qaysilarni aylanib chiqadi shu ko'rsatilgan (animatsiyani yasashga naqd yarim soat vaqtim ketdi)

mega_Uz ni fikridan keyin maqolani tahrirlab qidirish qismiga izoh qo'shdim.
Umuman search funksiyasiga 4 parametr beriladi.

from - qaysi shahardan
to - qaysi shaharga
search_step - qadamlar soni
found_distance - qidirish natijasida jami masofa

Bu yerda asosiy ro'lni o'ynayotgan narsa used o'zgaruvchisi, ya'ni u agar biz yo'l qidirishda bitta shahardan o'tgan bo'lsa shu shahardan o'tganimizni ko'rsatib turadi. Ikkinchi asosiy qisim esa

for(; i < from->distance_count; i++)
{
 cd = from->distances[i];
 if (cd->to->used == 1)
 continue;
 
 search(cd->to, to, search_step + 1, found_distance + cd->distance);
}

bunda from shahridan qaysi shaharlarga borish mumkinligidan kelib chiqib keyingi shaharlarga o'tamiz. Bu yerda «used == 1» bo'lganda shu shahardan tashlab o'tamiz. Ya'ni o'tilgan shahardan yana o'tmaymiz. Agar buni olib tashlasak dastur hech qachon javobni topmaydi. Aylanib yotaveradi ya'ni rekursiyaga tushib qoladi.

Qidirish rekursiya usulida amalga oshirilgan. Ya'ni A dan F borguncha search(A, F) => search(B, F) => search(C, F) => search(D, F) => search(E, F) ko'rinishida qayta qayta charirilaveradi. To eng kichigini topmaguncha. Tepadagi rasmga qarasangiz har bir search funksiyasi chaqirilgan qadamlar ko'ratilgan.

Shunaqa qilib umumiy kod ko'rinishi quyidagicha:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int city_count = 6;

struct city {
 char name;
 char used;
 int distance_count;
 struct city_distance** distances;
};

struct city_distance {
 struct city *to;
 int distance;
};

void _add_distance(struct city *from, struct city *to, int distance)
{
 int index = from->distance_count, i = 0;

 from->distance_count++;
 if (from->distance_count == 1) //birinchi marotaba
 from->distances = (struct city_distance**)calloc(1, sizeof(struct city_distance));
 else
 {
 for(; i < from->distance_count - 1; i++)
 {
 if (from->distances[i]->to->name == to->name)
 {
 from->distances[i]->distance = distance;
 from->distance_count--;
 return;
 }
 }

 from->distances = (struct city_distance**)realloc(from->distances, from->distance_count * sizeof(struct city_distance));
 }

 from->distances[index] = (struct city_distance *) malloc(sizeof(struct city_distance));
 from->distances[index]->to = to;
 from->distances[index]->distance = distance;
}

void add_distance(struct city *from, struct city *to, int distance)
{
 _add_distance(from, to, distance);
 _add_distance(to, from, distance);
}

char search_steps[10] = "";
char search_min_steps[10] = "";
int search_min_distance = -1;

void search(struct city *from, struct city *to, int search_step, int found_distance)
{
 int i = 0;
 struct city_distance * cd;
 search_steps[search_step] = from->name;
 search_steps[search_step + 1] = '\0';

 /**
 * Bu kod qo'shilsa qidirishlar sonini kamaytiradi

 if (search_min_distance != -1 && found_distance > search_min_distance)
 {
 return;
 }
 */

 if (from->name == to->name)
 {
 if (search_min_distance == -1 || found_distance < search_min_distance)
 {
 search_min_distance = found_distance;
 strncpy(&search_min_steps[0], &search_steps[0], 10);
 }

 printf("%s = %d\n", search_steps, found_distance);
 return;
 }

 from->used = 1;

 for(; i < from->distance_count; i++)
 {
 cd = from->distances[i];
 if (cd->to->used == 1)
 continue;
 
 search(cd->to, to, search_step + 1, found_distance + cd->distance);
 }

 from->used = 0;
}

int main() {
 unsigned char i;
 struct city** cities_list = (struct city **)calloc(city_count, sizeof(struct city));
 for(i = 0; i < city_count; i++)
 {
 struct city * c = (struct city *)malloc(sizeof(struct city));
 c->used = 0;
 c->name = 'A' + i;
 c->distance_count = 0;
 c->distances = NULL;
 cities_list[i] = c;
 }

 //A => B = 1000
 add_distance(cities_list[0], cities_list[1], 1000);
 //A => C = 1000
 add_distance(cities_list[0], cities_list[2], 1000);
 //A => D = 1500
 add_distance(cities_list[0], cities_list[3], 1500);
 //B => C = 1400
 add_distance(cities_list[1], cities_list[2], 1400);
 //B => D = 800
 add_distance(cities_list[1], cities_list[3], 800);
 //B => E = 1700
 add_distance(cities_list[1], cities_list[4], 1700);
 //B => F = 2600
 add_distance(cities_list[1], cities_list[5], 2600);
 //C => D = 700
 add_distance(cities_list[2], cities_list[3], 700);
 //C => F = 2800
 add_distance(cities_list[2], cities_list[5], 2800);
 //D => E = 1200
 add_distance(cities_list[3], cities_list[4], 1200);
 //D => F = 1600
 add_distance(cities_list[3], cities_list[5], 1600);
 //E => F = 900
 add_distance(cities_list[4], cities_list[5], 900);

 //A dan F gachasini topish
 search(cities_list[0], cities_list[5], 0, 0);

 printf("\n\nMIN: %s = %d\n", search_min_steps, search_min_distance);
 return 0;
}

Savollar bo'lsa marhamat.