Problem: Round Table Seating Arrangement

Clarification:

You are provided with a heuristic table representing the dislike percentages between

pairs of individuals, indicating the level of conflict or discomfort each person feels towards

others. The goal is to seat the individuals around a round table in the most suitable

arrangement to minimize conflict while ensuring that each person can talk to their

neighbors on the left and right.

Heuristic Table $($Dislike Matrix$)$:

The heuristic table provides dislike percentages between pairs of individuals, with higher

percentages indicating greater dislike or conflict. For example, a dislike percentage of $20\%$

between Person A and Person B indicates a low level of conflict, while a dislike percentage

of $80\%$ indicates a high level of conflict.

Cost Function:

In addition to the heuristic table, a cost function $f(n)$ is defined to incorporate the actual

cost of seating two specific individuals next to each other. Although it might be simpler

to use a constant cost $($e$.$g$.f(n)=1),$ the cost function used in this assignment is a Non$-$

Linear Dislike Cost function. The non$-$linear dislike cost function is described in the next

section.

Non$-$Linear Dislike Cost:

Define a non$-$linear function $f(x)$ that maps dislike percentages to costs. e$.$g$.,f(x)=x^2$

would make high dislike percentages have a quadratically higher cost.

f$($n$)=$

$//$ S

sum$($dislike$\_$percentages$\_$between$\_$neighbors$)+$

sum$($f$($dislike$\_$percentages$\_$between$\_$neighbors$))$

The aim of this

funnction is to penalize highly disliked pairs more severely than just a

constant of a linear mapping.

Objective:

Your objective is to determine which algorithm among Uniform Cost Search $($UCS$),$ Greedy

Search, and $A^{**}$ Search can find the best seating arrangement that minimizes conflict

based on the provided heuristic table and the Non$-$Linear Dislike Cost function.

Requirements:

Each person should be seated next to their neighbors on the left and right to

facilitate conversation.

The seating arrangement should form a closed loop, as it is a round table.

Tasks:

Implement the UCS, Greedy, and $A^{**}$ search algorithms to find the seating

arrangement.

Incorporate the Non$-$Linear Dislike Cost function into the search algorithms'

evaluation process.

Evaluate the effectiveness of each algorithm in finding the best seating

arrangement based on the conflict minimization objective.

Compare the obtained seating arrangements and discuss the strengths and

weaknesses of each algorithm in this context.

Present your findings, including the final seating arrangements and analysis of

algorithm performance, in a report.

Submission:

Submit your report detailing the implementation, results, and analysis of the algorithms'

performance.

The following dislike $=$ matrix represents the heuristic evaluation function $h(n)$

$//$ Below the Dislike matrix