Finding optimal graph structures is an important optimization problem that has applications in several

areas including machine learning itself, such as Bayesian Network Learning. The problem of Bayes$-$

Net Learning can be simplified as the vertex ordering problem. Given a set of vertices the goal is to

determine a vertex ordering with the minimum cost. Consider the network below, which can be

represented by the ordering $($B$,$ C$,$ A$)$:

Consider the following optimization problem. We are given vertices V$1,,$ Vn and possible parent

sets for each vertex. Each parent set has an associated cost. Let O be an ordering $($a permutation$)$ of the

vertices. We say that a parent set of a vertex Vi is consistent with an ordering O if all of the parents

come before the vertex in the ordering. Thus, $($C$,$ B$,$ A$)$ would be an inconsistent ordering for the above

network. Let mcc$($Vi$,$O$)$ be the minimum cost of the parent sets of vertex Vi that are consistent with

ordering O$.$ The task is to find an ordering of vertices O that minimizes the total cost of the network:

mcc$($V$1,$ O$)++$ mcc$($Vn$,$ O$)$:

As an example, consider that you are not given the network above. Instead you are given the vertices

A$,$B$,$ and C and their possible parent sets along with their cost as follows and given the task of finding

the minimium cost network.

The cost of ordering $($B$,$C$,$A$)$ is cost$($C$->\{$B$\})+$ cost$($A$->\{$B$,$C$\}))=2\mathrm{.}4+6\mathrm{.}3+1\mathrm{.}3=10$ whereas the

cost of ordering $($A$,$B$,$C$)$ is cost$($C$->\{$B$\})+$ cost$($B$->\{\}))=7\mathrm{.}5+6\mathrm{.}3+2\mathrm{.}4=16\mathrm{.}2$

Your task is to implement and experiment with the search algorithms$($BFS$,$ DFS$,$ UCS$)$ discussed in

class for finding a good ordering of the variables. Three datasets are made available for you to

experiment on $($in addition to the two simple examples described in this document$).$ You will implement

the search algorithms in Python and will submit a Python notebook that prints the minimum cost

ordering as well as its cost.

Consider the following short data file.

which represents the following example:

Consider the ordering $(5,3,1,4,2).$ With respect to vertex $1,$ the parent set $\{4\}$ is not consistent with

the ordering. The parent sets $\{\},\{3\},$ and $\{5\}$ are consistent with the ordering

The ordering $(5,3,1,4,2)$ has a total cost of $96\mathrm{.}093+121\mathrm{.}576+41\mathrm{.}775+36\mathrm{.}188+169\mathrm{.}802=$

$465\mathrm{.}435.$ whereas the ordering $(1,2,3,4,5)$ has a total cost of $153\mathrm{.}466+141\mathrm{.}022+107\mathrm{.}516+51\mathrm{.}680$

$+36\mathrm{.}508=490\mathrm{.}192$

this is dataset $1$ for eg do on this

$1,14,\{18\},131\mathrm{.}377$

$14,\{15,18\},125\mathrm{.}916$

$15,\{\},162\mathrm{.}685$

$15,\{1\},162\mathrm{.}408$

$15,\{14\},155\mathrm{.}061$

$15,\{1,14\},151\mathrm{.}99615,\{16\},154\mathrm{.}691$

$15,\{14,16\},149\mathrm{.}104$

$15,\{17\},161\mathrm{.}388$

$15,\{14,17\},154\mathrm{.}791$

$15,\{18\},159\mathrm{.}968$

$15,\{14,18\},154\mathrm{.}507$ The cost of ordering $(B,C,A)$ is $cost(C\{B\})+cost(A\{B,C\})$ whereas the

cost of ordering $(A,B,C)$ is $cost(C\{B\})+cost(B\{\})$

Your task is to implement and experiment with the search algorithms$($BFS$,$ DFS$,$ UCS$)$ discussed in

class for finding a good ordering of the variables. Three datasets are made available for you to

experiment on $($in addition to the two simple examples described in this document$).$ You will implement

the search algorithms in Python and will submit a Python notebook that prints the minimum cost

ordering as well as its cost.

Consider the following short data file.

which represents the following example:

Consider the ordering $(5,3,1,4,2).$ With respect to vertex $1,$ the parent set $\{4\}$ is not consistent with

the ordering. The parent sets $\{\},\{3\},$ and $\{5\}$ are consistent with the ordering$\{\},344\mathrm{.}233$

$1,\{\},153\mathrm{.}466$

$1,\{3\},96\mathrm{.}093$

$1,\{4\},97\mathrm{.}913$

$1,\{5\},99\mathrm{.}835$

$2,\{\},141\mathrm{.}023$

$2,\{3\},122\mathrm{.}446$

$2,\{4\},121\mathrm{.}576$

$2,\{5\},123\mathrm{.}398$

$3,\{\},169\mathrm{.}482$

$3,\{1\},112\mathrm{.}109$

$3,\{2\},150\mathrm{.}906$

$3,\{1,2\},107\mathrm{.}516$

$3,\{4\},51\mathrm{.}681$

$3,\{5\},41\mathrm{.}775$

$4,\{\},169\mathrm{.}482$

$4,\{1\},113\mathrm{.}929$

$4,\{2\},150\mathrm{.}036$

$4,\{1,2\},108\mathrm{.}982$

$4,\{3\},51\mathrm{.}681$

$4,\{5\},36\mathrm{.}188$

$5,\{\},169\mathrm{.}802$

$5,\{1\},116\mathrm{.}171$

$5,\{2\},152\mathrm{.}178$

$5,\{1,2\},111\mathrm{.}473$

$5,\{3\},42\mathrm{.}096$

$5,\{4\},36\mathrm{.}508$