Local Search: Satisfaction Vs Optimization Part-1

[@vetrimaaran1513]

09:11 So whenever someone gives u constraints and asks to satisy all the constraints it is a satisfaction problem. Thats how u find the right goal. But u can also remodel it as an optimisation problem just by introducing an objective function. Again u have constraints but along with it, u also have a function which maximises the constraints that are satisified(thereby reaching the optimal goal). For example, if u pass on a state to that objective function, it will say-----“BRO THE STATE U PROVIDED does not satisy all the constraints, so most prolly it is a bad solution. Thereby helping you to conclude whether a particular state is a good solution or a worst solution.

[@vetrimaaran1513]

04:44 1. Till now the algorithms we saw were worried much about finding the path. That is, "how we reach the goal" mattered. THAT WAS ONE KIND OF A PROBLEM.(Arad-to-Sibiu-to-Bucharest, it was very important to find a good path over there) 2. But there are a certain category of problems where THE PATH is not important. But the final state is important. (U need to familiarize urself with chess before reading on) For example the N-queens problem. Lets assume 8 queens problem in a chess board. This is the challenge. U have to place 8 queens on a chess board such that they don't cut horizontally vertically or diagonally. ( A queen has the ability to move in these 3 directions only but it cannot attack a piece that is placed in L-shape from it) Queens should be placed in L-shape from each other, that is the only way, to prevent every queen from being attacked. So here, the state is important(the final image of 8 queens). Path doesn’t matter-----we don't give a damn about which queen is placed 1st, which queen is placed 2nd. We just want the final arrangement where each queen doesn't attack each other. That's where local search comes in. It searches thru ALL THE FINAL COMPLETED states. (w.r.t N-queens problem it searches thru many many 8 queen arrangements until it finds that one state where queens don't attack each other). (Some completes states are good but some are worst)

[@techedit6284]

🤯

[@techedit6284]

Tq

[@vetrimaaran1513]

16:23 In local search we said, we search thru different completed states and come up with the best state that could prolly be the solution. But if u want a path as a solution. That also can be done thru local search. But instead of searching thru completed states, we search thru completed paths to come up with the best path.

[@yashkumar-hg8lb]

First View

[@naive-fleek7420]

party when?

[@iWontFakeIt]

@@naive-fleek7420 party mila??

[@naive-fleek7420]

@@iWontFakeIt still waiting

[@iWontFakeIt]

@@naive-fleek7420 😂🥱

[@garbagebin3693]

@@naive-fleek7420 if you get invited to the party, let me know too 😌