Fan nomi: Algoritmlarni loyihalash Laboratoriya ishi 4 Mavzu

TOPSHIRIQ:

Kommivoyajer masalasini yechishning algoritmi va dasturini tuzing. Quyidagi ma’lumotlar asosida dasturni bajaring va hisobot yozing. Variant raqami talabaning jurnaldagi tartib raqamiga mos bo’lishi kerak.

10)		3	1	2	3
	8		3	4	3
	3	1		6	2
	1	8	9		4
	3	7	4	1

Dasturi:

#include

using namespace std;

#define V 5

int travllingSalesmanProblem(int graph[][V], int s)

{

vector vertex;

for (int i = 0; i < V; i++)

if (i != s)

vertex.push_back(i);

int min_path = INT_MAX;

do {

int current_pathweight = 0;

int k = s;

for (int i = 0; i < vertex.size(); i++) {

current_pathweight += graph[k][vertex[i]];

k = vertex[i];

}

current_pathweight += graph[k][s];

min_path = min(min_path, current_pathweight);

} while (next_permutation(vertex.begin(), vertex.end()));

return min_path;

}

int main()

{

int graph[][V] = { { 0, 3, 1, 2, 3 },

{ 8, 0, 3, 4, 3 },

{ 3, 1, 0, 6, 2 },

{ 3, 7, 4, 1, 0 } };

int s = 0;

cout << travllingSalesmanProblem(graph, s) << endl;

return 0;

}

Hisobot.

Mavzuga doir nazariy ma’lumotlar keltirib o’tildi. Shuningdek, Kommivoyajer usuli orqali berilgan jadval asosida eng qisqa xarajat talab qiladigan masofa topildi. Bu usul hayotimizda juda asqotadi. Uni dasturiy ko’rimishini yaratish esa undan osongina foydalanishga imkon beradi.

FOYDALANILGAN ADABIYOTLAR

1. Kulakov A.G., Lando S.K., Semyonov A.L., Shen A.X. Algoritmika. V-V II sinflar. Moskva: Drofa, 1997.

2. Boltayev B. Abduqodirov A., Taylaqov N., Mahkamov M., Azamalov A., Xafizov S. Informatika va hisoblash texnikasi asoslari. 9-sinf. T.: Cho lpon, 2006.

3. Boltayev B., Mahkamov M., Azamatov A. Informaiikadan olimpiada masalalarini yechish. Metodik qo'llanma, T: 2004.

4. Boltayev B., Mahkamov M., Azamatov A. Informalikadan olimpiada masalalarini yechish-2. Melodik qo'llanma, Toshkent, 2004.

5. B.Boltayev, A.Abduqodirov, N.Taylaqov, M.Mahkamov, A.Azamalov, S.Xafizov. Informatika va hisoblash texnikasi asoslari. 9-sinf. T.: Cho'lpon, 2006.